Dynamic computation migration in DSM systems

摘要

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 moredynamic.