The design of a control unit and parallel algorithms for a SIMD computer

The Reconfigurable Processor Array (RPA) is a parallel computer operating in SIMD mode. One disadvantage of processor arrays is the fixed structure to which users have to adapt their applications. The RPA design aimed at reducing this problem by creating an array which through reconfiguration could be applied to a wide variety of problems without losing efficiency. This is achieved by allowing processing elements within the array to be linked so that processors of different sizes can be created. The first part of this thesis presents a contribution to the RPA project, which is the design of a microprogrammable control unit for the system. The control unit design allows the parallel execution of scalar and array operations. The scalar unit uses a 32-bit transputer. All array operations are executed by the processor array under control of a microcontroller. The design of the interface between these two units presents improvements over previous designs. The interface is based on a dual-port RAM where the transputer maintains a linked list of processes waiting executing by the array. The flexibility of the interface facilitates the integration of array operations into the OCCAM model of concurrency. The second part of the thesis also deals with the problem of the fixed structure of the arrays, but from a programmer's point of view. Array languages usually introduce constraints that reflect the parallelism to which they were designed. This makes portable programs difficult to write. This part of the thesis presents algorithms that lift some of these restrictions. The definition of the algorithms (SPREAD, RESHAPE, COMPRESS, EXPAND) was taken from APL and FORTRAN 8X. (D82615)