“Post-game analysis”: a heuristic resource management framework for concurrent systems
Jerry C. Yan · 1989
The effective use of multiprocessors depends critically on the ability of their resource management systems--to properly trade off communication loss and concurrency gain, exploit behavioral characteristics of the application programs, and take advantage of specific hardware features of the multiprocessor. Unfortunately, the performance of many proposed resource management strategies can only be evaluated indirectly by simple objective functions (such as execution cost or mapping cardinality). Research has been conducted to determine how distributed computations can be mapped onto multiprocessors to minimize execution time. The approach proposed here, known as POST-GAME ANALYSIS, offers an unconventional alternative to reduce program execution time. Program-machine mapping is improved in-between program executions. Instead of using simple abstract models, post-game analysis utilizes actual timing data gathered during program execution. Program execution time is reduced based on many optimization sub-goals. Because heuristics are applied to improve the current mapping and resolve conflicting sub-goals, post-game analysis can be incrementally refined and tailored to specific applications and architectures. The performance of post-game analysis has been compared against other strategies using various program structures and multiprocessor models. Results obtained from simulations show that it out-performs the speed-up obtained based on random placement, load-balancing as well as clustering algorithms by 15%.