Fellow 1992-93

Gul A. Agha

Computer Science

Foundations of Scalable Concurrent Computing

Computer Science is at the threshold of a major advance which will allow dramatic increases in computation power. Conventional computers employed a single processing unit (the "brains" in a computer). Current efforts have generally increased the number of processing units to small numbers of processors in a single concurrent computer. In some cases, a large number of extremely weak processing units have been organized in rigid ways. For example, the CM2 computer has 64,000 simple processors which may manipulate only a single bit; furthermore, it requires the same instruction to be carried out on all processors at a given time. Such restricted architectures are very special purpose—they allow only a special class of problems to be solved. On the other hand, Professor Agha's project focuses on large ensembles of relatively powerful autonomous computers.

As processing units have become cheaper, it is now feasible to consider linking greater numbers of powerful units to carry out a computation. For example, Japan is launching a ten-year national project which proposes to build a computer consisting of a million independent processors. A significant difficulty in using such massively parallel architectures is programming. A given problem needs to be divided into millions of sub-problems and their solutions have to be coordinated. Because of communication and coordination costs, the speed with which a problem can be solved does not grow linearly with the number of processors employed. If a problem is not structured in a way which can efficiently utilize the computational resources, performance may be worse than with a sequential processor.

The project will develop a methodology for specifying and building large-scale systems. Different organizational structures for programming large-scale ensembles of computers will be studied. Such structures include hierarchical, competitive, and cooperative ones. The project will characterize computational efficiency and scalability of organizational structures for computer systems. It will further develop the programming language constructs necessary to provide abstract specifications which free a system designer from implementing the details of the coordination structures.