Name
Abstract | ||
|---|---|---|
We describe dynamic computation migration, the runtime choice between computation and data migration. Dynamic computation migration is useful for concurrent data structures with unpredictable read/write patterns. We implemented it in MCRL, a multithreaded DSM system that runs on the MIT Alewife machine and Thinking Machines' CM-5. We evaluate two dynamic migration heuristics relative to data migration. On a concurrent, distributed B-tree with 50% lookups and 50% inserts, the STATIC heuristic improves performance by about 17%, on both Alewife and the CM-5. The REPEAT heuristic generally performs better than the STATIC heuristic. On Alewife, with 80% lookups and 20% inserts, the REPEAT heuristic improves performance by 23%; on the CM-5, it improves performance by 46%. Our results apply to concurrent, dynamic data structures whose access patterns are only known at runtime. For regularly accessed data structures, static methods will always be applicable, but we expect future applications to be more dynamic. |
Year | DOI | Venue |
|---|---|---|
1996 | 10.1145/369028.369119 | SC |
Keywords | Field | DocType |
dynamic data structure,runtime choice,static heuristic,concurrent data structure,mit alewife machine,dynamic computation migration,repeat heuristic,dynamic migration,data migration,dsm system,accessed data structure,history,measurement,distributed computing,concurrent data structures,concurrent computing,data structures,distributed shared memory,data structure,replication,coherence | Data structure,Heuristic,Computer science,Parallel computing,Heuristics,Concurrent data structure,Dynamic data structures,Data migration,Computation,Distributed computing | Conference |
ISBN | Citations | PageRank |
0-89791-854-1 | 8 | 1.08 |
References | Authors | |
13 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wilson C. Hsieh | 1 | 2532 | 261.94 |
| M. Frans Kaashoek | 2 | 15558 | 1966.90 |
| William E. Weihl | 3 | 2614 | 903.11 |