In the area of programming languages, research is underway to find alternatives to languages like FORTRAN and C which were designed for sequential computers. These languages are designed around the concept of storing into and reading from memory locations. In contrast, functional languages and logic programming languages are designed around the concept of operations on values, rather than on storage locations. These languages appear to be more suitable for programming parallel machines. This project is unifying functional and logic programming languages and giving these hybrid languages precise operational and denotational semantics. To execute programs in these languages, the project is designing a parallel architecture that can exploit parallelism at all levels in the program. Existing multiprocessor architectures can exploit what is called "coarse-grain parallelism" - for example, they can run different iterations of a loop in parallel. This approach misses out on 'fine- grain' parallelism - for example, parallelism among the instructions of a loop iteration. Dataflow architectures can exploit fine-grain parallelism but they do so at the price of considerable synchronization overhead during program execution. This project is defining a parallel architecture that can exploit both fine-grain and coarse-grain parallelism without suffering the runtime overhead of pure dataflow machines. Compiling programs for this architecture involves decomposing a program into many processes and scheduling the operations within each process. Process decomposition strategies based on exploiting spatial locality of reference are being studied - as far as possible, code is placed on the same processor as the data it manipulates. This style of process decomposition is useful even for conventional architectures like the Intel iPSC/2 and the BBN Butterfly in which remote memory accesses take much longer than local memory accesses. In addition, algorithms for static scheduling of loops and for software pipeling ofloop iterations are being developed.
