Automatic Scheduling for Cache Only Memory Architectures Extended Abstract
R. Moore, Bernd Klauer, Klaus Waldschmidt, Johann Wolfgang Goethe-University · 1998
For parallel and distributed systems to gain more acceptance than they have to date, they will need to be scalable, affordable — but most importantly, they must be made as easy to program as sequential systems. Ideally, we would like to be able to take programs written in conventional languages and recompile them for parallel architectures, thus freeing the programmer from all additional effort above and beyond that necessary to program a conventional computer. This in turn implies that either the compiler, the hardware, or both, must address the fundamental issue of distribution. This problem is two-fold: Both data and computation must somehow be distributed. The problems of data distribution and computation distribution have traditionally been addressed separately. On the one hand, Cache Only Memory Architectures (COMAs) provide an automatic and transparent form of selfdistributing Distributed Shared Memory (DSM) [3]. In this model, each processor has a local memory which has been augmented so that it acts like a giant, slow cache. A memory augmented in this fashion is called an “attraction memory”; Data migrates from one attraction memory to another based on demand (attractive forces) and congestion (dissipative forces). However, the COMA literature unanimously treats computation distribution as the responsibility of the application program. On the other hand, the dataflow paradigm and later, the multithreaded architectures provide us with a simple way to attack the scheduling problem. Each program is represented as a graph whose vertices represent threads, and the time at which a thread is executed is determined by the availability