I have met JI, Yu, another CCF distinguished doctoral thesis award recipient, in Xining. He is very confused about my doctoral thesis: How could you make such a complex system into fractals? You really did that at Cambricon? I explained to him that fractalness is very primitive, rather than being made by me for thesis writing. In the talkshow of the day, I redefined the concept of Fractal Parallel Computing: Fractalness (parallel computing) is the primitive property of parallel computed problems, that there exists a finite program to control the arbitrarily scaled parallel machines, and to solve the problem of any size in finite time.

It is not only Doctor JI. Many peers have raised similar concerns. Indeed, it is showing that my works are still very preliminary. I must admit that fractal machines are yet hardly useful in practice to any other developers. But take an advice from me surely: if your system is not fractal, you should be really very cautious!

Allowing separate programming over a parallel machine can make the situation awkward: The excessive programs serve as advice strings to the computation.

Take an MPMD model for example. Since I have nodes to program and work in parallel, I can hardcode one bit of information into each node. At the very begining of the computation, I can gather the bits, forming an -bit natural number and distribute it to all nodes. Let us denote that number as . Trivially, can represent values up to .

Why would that matters? is smuggled into the programs, which depends on the scale of the parallel machine, which is further scalable with the problem size , thus introduced non-uniformity. Say, we let indicate the number of Turing Machines of descriptive size that halt on empty tapes. Then we get the following algorithm immediately:

  1. Input as the description of a TM ( bit).
  2. Gather and distribute the value of .
  3. .
  4. Parallel-for each :
    1. Simulate on an empty tape until halting.
    2. Increase atomically.
    3. If , abort the parallel for.
  5. Return whether the -th simulation is finished or aborted.

It decides the Halting problem in finite time.

If your system does not allow that (deciding non-recursive problems), it is already fractal, although not necessarily in the identical form as in my thesis. The fundamental problem is that, the excessive programs are harmful. Theoretically they cause the non-computable problems being computable on your system; Practically they raise various problems, including the rewriting every year problem we encountered in Cambricon (Cambricon-F: Machine Learning Computers with Fractal von Neumann Architecture). Fractal computing systems are against these bad practices.

I hope the above argument makes the point clear.

Reference