DAG-consistent distributed shared memory
| Autor: | Charles E. Leiserson, Robert D. Blumofe, Matteo Frigo, Keith H. Randall, Christopher F. Joerg |
|---|---|
| Rok vydání: | 2002 |
| Předmět: |
Distributed shared memory
Page fault Computer science CPU cache Consistency model Thread (computing) Parallel computing Cilk Directed acyclic graph computer.software_genre Runtime system Strassen algorithm Multithreading Operating system Concurrent computing Memory model computer computer.programming_language |
| Zdroj: | IPPS |
| DOI: | 10.1109/ipps.1996.508049 |
| Popis: | Introduces DAG (directed acyclic graph) consistency, a relaxed consistency model for distributed shared memory which is suitable for multithreaded programming. We have implemented DAG consistency in software for the Cilk multithreaded runtime system running on a CM5 Connection Machine. Our implementation includes a DAG-consistent distributed cactus stack for storage allocation. We provide empirical evidence of the flexibility and efficiency of DAG consistency for applications that include blocked matrix multiplication, Strassen's (1969) matrix multiplication algorithm and a Barnes-Hut code. Although Cilk schedules the executions of these programs dynamically, their performances are competitive with statically scheduled implementations in the literature. We also prove that the number F/sub P/ of page faults incurred by a user program running an P processors can be related to the number F/sub 1/ of page faults running serially by the formula F/sub P//spl les/F/sub 1/+2Cs, where C is the cache size and s is the number of thread migrations executed by Cilk's scheduler. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|