Professor Uzi Vishkin Featured in Communications of the ACM Magazine

Dr. Uzi Vishkin presented a “counterpoint” article in the September edition of Communications of the ACM (Association for Computing Machinery). The Communications is distributed to all members of the ACM, which is the world’s largest professional organization of computing professionals. It is an educational and scientific society that provides resources for advancing computer science research.

The “point” viewpoint responded to by Vishkin was written by Dr. William Dally, an adjunct professor at Stanford University and chief scientist and senior vice president of research at NVIDIA. In his article, entitled “On theModel of Computation: Point: We Must Extend Our Model of Computation to Account for Cost and Location,” Dally discusses the traditional models of measuring the complexity of algorithms as RAM (random-access memory) and PRAM (parallel RAM) that treat all computing operations as unit cost. He opines that such models were appropriate during the early days of computing as the costs of arithmetic and communication were basically comparable then. He then asserts that costs of arithmetic has been considerably reduced with current semiconductor technology,

He concludes by saying that adjustments to the PRAM model could fix these issues by assigning different costs to arithmetic operations and memory access. Arithmetic operations would remain at their unit cost, but memory operations would have a higher cost, proportional to distances traversed: as “on chip roads” often obey a Manhattan-avenue/street-like grid structure, the distance between two points can be thought of as street length plus avenue length to be traversed. Allowing for the true costs of computations, an upgraded model, PECM (parallel explicit communication model), would allow for the design of more efficient computations, resulting in a reduction of computing’s carbon footprint.

Vishkin’s counterpoint, “On the Model of Computation: Counterpoint: Parallel Programming Wall and Multicore Software Spiral: Denial Hence Crisis,” presents a nearly diametrically opposite position. It has been nearly two decades since multicore processors fully replaced single core ones on desktops, laptops and mobile devices. A recognized founder of the main theory of parallel algorithms, the working assumption motivating Vishkin’s 40+ year research career has been that parallel algorithms and programming will be a hardship for most programmers. Therefore, parallel computer systems must be designed to maximally ease this hardship, and parallel algorithms researcher should guide hardware designers for how to best do it, which is why he devoted the first stage of this career to parallel algorithms. Vishkin notes the dearth of programming today’s multicores for their parallelism and suggests that this has badly handicapped their utility. Furthermore, he views this dearth and the apparent perception that programming such systems is simply too difficult, as a vindication of both his working assumption and his overall research strategy of first studying parallel algorithms and only then computer architecture. Vishkin lists the many benefits of PRAM, including: its simplicity; its ability to import from mathematics mathematical induction for describing algorithms and proving their correctness; and competitive support by the unique PRAM-On-Chip XMT computer system platform he invented and led prototyping in hardware and software with 16 graduate students at UMD. Buttressed by the breakthrough UMD XMT demonstration, he concludes that PRAM is so resilient that it is a clear role model for programming general-purpose manycore CPUs, as it enables overcoming the grave scarcity of parallel programmers, as well as cost-effective development of future applications.

While in agreement with Dally’s PECM proposal for a limited number of specialized cases, Vishkin believes that Imposing the PECM implied optimizations on most programmers would be an immense undertaking, therefore it would not be practical. In addition, he notes that he is not aware of any demonstrated success of PECM for general-purpose programming.

The full articles can be read at these links:

"Point" article by William Dally: https://cacm.acm.org/magazines/2022/9/263792-on-the-model-of-computation-point/fulltext

"Counterpoint" article by Uzi Vishkin: https://cacm.acm.org/magazines/2022/9/263793-on-the-model-of-computation-counterpoint/fulltext

Published September 26, 2022