SHF:Small:RUI: Observationally Cooperative Multithreading

Harvey Mudd College, Claremont CA

Investigators

Abstract

Today's multicore processors are often underutilized because programmers lack tools and techniques to program them effectively. To understand the problem, imagine that a microprocessor is like a restaurant kitchen. For years, processor designers improved execution speed, replacing the chef with one who can work even faster. Because this strategy has physical limits, hardware vendors are turning to multicore CPUs, akin to multiple chefs. Some problems adapt easily to multiple cores; if you need to bake 16 identical cakes, it's easy to use 16 chefs in separate kitchens (i.e., symmetric parallelism). But if you need to prepare a complex banquet (i.e., irregular parallelism), the many tasks can require significant coordination. One mistake (e.g., two chefs using the same bowl at the same time) and the results may be disastrously wrong. Experience has shown that few programmers can foresee and avoid all possible coordination issues ahead of time. This project develops the approach Observationally Cooperative Multithreading (OCM) for solving problems on parallel machines. OCM makes it easier to write correct code, while allowing speedup on from multiple processing cores. Because of its simplicity, OCM could make parallelism and concurrency more accessible to a broad audience, including introductory students. Specifically, in programs written for the well-understood cooperative multithreading (CM) model, subtasks take turns and execute one at a time. This approach rules out conflicts between subtasks and simplifies programming and debugging. OCM takes these same programs but runs them on modern multicore machines, executing subtasks simultaneously (and hence more efficiently) when there are no conflicts. This research, extending preliminary work on OCM, will involve 18 undergraduate students over three years. They will help design, develop and evaluate practical OCM implementations using techniques such as Transactional Memory and Lock Inference, addressing the concerns both of the parallel-programming community (who value demonstrated performance) and of the CS education community (who value ease of use and desperately need a simpler introduction to concurrency and parallelism).