The N-computer: A data-flow bulk synchronous machine for data parallel programs.

There are two fundamental problems which a researcher in the field of general purpose parallel computing is facing. One is to develop a framework for portable and easy to write parallel applications. The other is to design a scalable parallel machine upon which the parallel applications can be executed efficiently and economically. To solve the first problem, a portable software platform (PSP) for data parallel high level languages like Fortran 90, F-code, has been developed by the members of the Computer Systems Research Group at the University of Surrey. F-code can be considered as a machine independent intermediate level representation of a data parallel program. This thesis addresses the second issue, i.e., the design of a scalable parallel machine, the N-computer, while critically examining and then refining the definition of F-code. F-code is considered as a problem domain for the N-computer. Two extremes of the design space for a parallel machine, i.e., the conventional von-Neumann and dataflow, are not suitable to implement a design of the machine according to the specifications developed. The conventional approach is unable to address the two major issues of a parallel machine, i.e., synchronization and latency, at the same time. When a solution to solve one problem is found, the other problem becomes worse. Evolution in the design of dataflow machines has solved the major problems facing those kinds of architectures, such as the implementation of a waiting/matching store and scheduling of macroactors instead of single instructions. By scheduling a macroactor which contains code for more than one instruction for which there is no remote communication, the need for explicit synchronization can be eliminated. However, the problem of token recycling and the need for the I-structure storage to access variables, which need a three state synchronizer for each of its operation, are still remained unsolved. Both are quite expensive in the modern dataflow machines. It is observed that the dataflow bulk synchronous machine (DFBSM) model can address these two problems. The N-computer is designed on top of the DFBSM model for data parallel languages. The implementation not only enjoys the benefits of DFBSM, but is also favoured with the regular structure which is normally available in a data parallel application. The design of the N-computer is described at system level. Each processing node is broken down into six major sub-systems. The logical organization of each sub-system and its functioning and the interaction with other sub-systems are discussed. The addition of certain features in the organization of these sub-systems is argued. Then the ways to execute each F-code function are discussed. In other words, this thesis presents the system level design and functioning of the N-computer for its complete operation cycle, and demonstrates the ways to execute an F-code program on an N-computer. A plan to build soft prototype of the N-computer system is presented. A major portion of the plan is implemented in software. A simulation of data distribution strategies is also implemented and presented. Due to different communication patterns in programs, it is not possible to statically fix the distribution strategy for optimal execution of all the programs. Different programs may need to be distributed in different ways. By simulating different distribution strategies for a given program, an optimum way to distribute objects can be selected. The N-computer is capable of dynamically adopting a distribution strategy for each activity in an activity tree depending upon the information available in the activity. An important phase for the design of the N-computer was a thorough understanding of the problem domain, i.e., F-code. For that purpose, an F-code interpreter, F-SIM, was implemented in C. The implementation of F-SIM is described. F-code is also examined as a PSP for data parallel high level languages and compared with other potential PSPs. A PSP must preserve certain features available in a data parallel application to preserve the efficiency of an implementation. Although, F-code preserves most of them, there is a need to preserve primitive type sizes. To see whether F-code semantics are powerful enough to compile data parallel high level languages, like Fortran 90, the definition of F-code is examined qualitatively. In the light of this study, a modified definition of F-code functions is suggested