Zhijing George Mou
Bibliography

English version translation © 2001 M.E. Sharpe, Inc., from the Chinese original, in Contemporary Chinese Thought, vol. 32, no. 4, Summer 2001, pp. 17–36. cached copy here.

TLDR: This paper argues that all people are created equal.

M. E. Sharpe: "This essay was originally published on January 18, 1967 in the premiere issue of the capital’s Journal of Middle Schools Cultural Revolution. Its first draft was completed in August 1966, and it was subsequently revised in November 1966.

"The author of this essay, Yu Luoke, was a young worker and thinker in Beijing. Because of this writing, he was executed by the government in 1970."

Abstract: An overview of the language, covering Divacon primitives and simple programming constructs that are referred to as functional forms, is given. Two divide-and-conquer programming constructs are discussed. Divacon style programming is demonstrated for a number of scientific applications. Some interesting equivalences and transformations between Divacon programs are examined. Implementation and performance are briefly considered.

Abstract: The goal is to make Divide-and-Conquer algorithms suitable for implementation on hypercube-like parallel architectures, such as the Connection Machine, even if the original algorithm implies a division function that is not the left-right division and/or communication pattern that cannot be implemented by direct-neighbor communication

Abstract: The paper introduces the notion of a DC Transpose, which is a remapping of data on a mesh, using a global routing mechanism such as the global router on the Mas-Par MP-1, to solve divide-and-conquer algorithms.

Abstract: The authors present a new parallel algorithm, based on the divide-and-conquer (DC) strategy, for solving tridiagonal systems, and show that for the binary hypercube architecture, the communication complexity of their DC method is the lowest among all, and therefore the most efficient tridiagonal solver for communication-expensive massively parallel hypercube computers.

Abstract: We present a formal model for the analysis of communication networks in parallel computers. Unlike most others, our model focuses on the transmission delays as opposed to the propagation delays of communication patterns. The model allows all symmetric communication networks to be examined by their spectrums and characterized by their transmission dimensions. A min-cut transformation is introduced as a tool for the spectrum analysis, which reduces any symmetric network to the same canonical form. Parallel architectures with different topologies can then be easily compared and evaluated.

(For review on lattice gas automata see The Classical Lattice-Gas Method by Jeffrey Yepez 1999, DTIC/ADA455835.pdf).

TLDR: This paper proposes an alternative model called Individually Distributed Object (IDO) which allows a single large object to be distributed over a network, thus providing a high level interface for the exploitation of parallelism inside the computation of each object which was left out of the distributed objects model.

Abstract: Distributed Objects (DO) as defined by OMG’s CORBA architecture provide a model for object-oriented parallel distributed computing. The parallelism in this model however is limited in that the distribution refers to the mappings of different objects to different hosts, and not to the distribution of any individual object. We propose in this paper an alternative model called Individually Distributed Object (IDO) which allows a single large object to be distributed over a network, thus providing a high level interface for the exploitation of parallelism inside the computation of each object which was left out of the distributed objects model. Moreover, we propose a set of functionally orthogonal operations for the objects which allow the objects to be recursively divided, combined, and communicate over recursively divided address space. Programming by divide-and-conquer is therefore effectively supported under this framework. The Recursive Individually Distributed Object (RIDO) has been adopted as the primary parallel programming model in the Brokered Objects for Ragged-network Gigaflops (BORG) project at the Applied Physics Laboratory of Johns Hopkins University, and applied to large-scale real-world problems.

Although this paper by Google is famous and considered the pinnacle of parallel processing, a principle that any solution coming from a company like Google must be unacceptable suggests it may have flaws. "How do you know a solution is bad? If it's from Google, that's enough." Reading between the lines, I notice that the paper fails to even express the basic mathematical facts of MapReduce, namely that (1) it is a higher order function (a function that takes functions as input and returns a function as output which may then be applied to data), that this particular higher-order function specifically requires (2) a unary function (call it map), and (3) an associative binary function, (call it reduce); that (4) the returned function applies the unary, map, function to each element of the input data vector, and the associative binary, reduce, function to the vector of map outputs, and, (5) obviously yet perhaps not obviously enough for these authors and their employer, an associative operation to summarize a vector of data can be applied using recursive even-odd division or left-right combination after division and therefore completed in log N time. For example in 3 time-steps + can be applied to 8 elements using ((a+b)+(c+d))+((e+f)+(g+h)) rather than using 7 time-steps to equivalently calculate (((((((a+b)+c)+d)+e)+f)+g)+h). Use recursive parallel decomposition!

To reiterate, although some parallelism is achieved it fails to take advantage of the deep parallelism of a recursive divide-and-conquer approach, so that log N time is not achieved. On the one hand, after a single M-ary division of the data, a number of linear-time subtasks are scheduled. In case of the map operation which is non-combinatory, if all the available processors are busy doing essential map work, that's all the parallelism available: all must be done independently and no ordering or building up of results saves operations. On the other hand, an associative reduce operation applied to the whole can be done either in head-tail (as they do) or left-right (as would be better) approaches. Let's count. Each of those could be done on 1 or M subdivisions of the map outputs, yielding O(N) vs O(log N) time results on 1 subdivision, or O(N/M) vs O(log(N/M)) time results on M subdivisions ignoring final combination/reduction. With N ~ 2^33 and M = 1, N vs log N = 2^33 vs 33; whereas, with N ~ 2^33 and M ~ 2^10, we still find N/M ~ 2^23, while log(N/M) ~ 23. That is, Dean's splits indeed save 3 orders of magnitude but nothing like log(2^23/23) ~ 23-5 = 18 orders of magnitude saved by recursive left-right division. The point is that an associative reduce function applied to a large dataset using left-right decomposition enables log N time, as an absence of clear thinking will indeed fail to notice, however obvious it may be. This is made explicit in a Divacon definition:

Here an associative binary operation, reduce, is given as the combination function, which combines outputs while moving back up the computation tree after map has separately processed each input element at the computation tree's leaf nodes. A left-right-subdivided computation tree on 10^7 leafs is only 23 levels deep, reducing the task to O(log N) = 23 time steps, vastly less than the vaunted O(10^7) time steps.

Hence even division once over processors fails to achieve anywhere close to such improvements, despite admittedly achieving, say, 1000x improvements. Recursive parallel decomposition is the trick, which the Google paper misses.

Next, parallel communication opportunities are ignored (cf Optimal mappings, here), although tree based communication for that subset of communications that may be sent and delivered within sub-branches simultaneously, the basic Ethernet link design used in Google's pride here implies queued and sequential communications rather than simultaneous and parallel communications at least within the set of processors, or sets of sets of processors, so linked. And when communications are not perfectly local, the queueing/blocking bottlenecks at the top of the tree not only remain but are multiplied by combinatorically.. Therefore queuing and blocking are implicated and transmission characteristics are vastly narrowed. See also the 1995 Min-Cut paper, above; indeed do a Min-Cut transform on Google's network and you will see the relative limitations.

Abstract: The CC paradigm is implemented in Haskell as a modular, higher-order function, compiled into low-level Haskell threads that run on a multicore machine, and performance benchmarks confirm the theoretical analysis.

Comments from George: The method of K-M Shuffle from the Optimal Mappings paper is in fact the same as DST itself. Furthermore given K=3 and M=2 then a point cloud of 3D points (LIDAR or optical) can be mapped to a key or point cloud of 2D keys using DST, and then the usual convolutional neural network (CNN) which is excellent at 2D image classification but terrible at 3D image classification can be used to classify 3D-to-2D-DST-transformed 3D point clouds of 3D objects such as car, tree, pedestrian, bicycle, sign, pole, etc., and although the images viewed in 2D do not remotely appear to a human viewer as cars trees etc., still the CNN is great at learning to recognize those object classes from the transformed-to-2D data.

However the field is unaware of this amazing capability and may remain so indefinitely. Indeed there are many beautiful properties of DST, but it seems impossible to explain them to anyone so that they truly understand them all.

TV note: asking deepseek ai about this in general terms after George mentioned it to me, the AI found this paper with this title given at this conference, which does appear to be real, but it hallucinated the actual publication which is not actually in those proceedings. And George for his part says he has a presentation of it, but himself does not have a full paper.

Notes on the here.