Embedding tree computations into the RAW chip
Adrian Mihail Soviani · DSpace@MIT (Massachusetts Institute of Technology) · 2002
The main goal of this thesis is to provide coarse grain parallelism for the RAW chip. Coarse grain parallelism can be expressed by using instrumented function calls which are queued and executed on other processors. Function calls are reassigned to adjacent processors only. Subsequently, a computation tree is dynamically embedded into the processor mesh (Chapter 3). A C library interface was developed to provide this mechanism: applications can spawn function calls, and wait at synchronization points (Chapter 4). Two imple-mentations of the spawn interface were built as part of the thesis project: i) a system that runs on the RAW chip using interrupting messages to implement work scheduling and synchronization (Chapter 5); ii) a generic spawn library based on POSIX threads that uses shared memory and locking (Chapter 6). Embedding computation trees into 2D processor meshes proved to be successful for a selection of tree structures and mesh sizes. Two models were used for testing: a perfect binary tree, and a Fibonacci tree.