Multicore-oblivious Algorithms

Rezaul Alam Chowdhury of Boston University presented a lecture on March 28, 2011 from 10:00 am to 11:00 am in room 1116 of the Klaus Advanced Computing Building on the Georgia Tech campus.Runtime: 51:10 minutes.Multicores represent a paradigm shift in general-purpose computing away from the von Neumann model to a collection of cores on a chip communicating through a cache hierarchy under a shared memory. Designing efficient algorithms for multicores is more challenging than that for traditional serial machines, as one must address both caching issues and shared-memory parallelism. As multicores with a wide range of machine parameters rapidly become the default desktop configuration, the need for efficient, portable code for them is growing. This talk will mainly address the design of efficient algorithms for multicores that are oblivious to machine parameters, and thus are portable across machines with different multicore configurations. We consider HM, a multicore model consisting of a parallel shared-memory machine with hierarchical multi-level caching, and we introduce a multicore-oblivious (MO) approach to algorithms and schedulers for HM. An MO algorithm is specified with no mention of any machine parameters, such as the number of cores, number of cache levels, cache sizes and block lengths. However, it is equipped with a small set of instructions that can be used to provide hints to the run-time scheduler on how to schedule parallel tasks. We present efficient MO algorithms for several fundamental problems including matrix transposition, FFT, sorting, the Gaussian Elimination Paradigm, list ranking, and connected components. The notion of an MO algorithm is complementary to that of a network-oblivious (NO) algorithm, recently introduced by Bilardi et al. for parallel distributed-memory machines where processors communicate point to-point. Indeed several of our MO algorithms translate into efficient NO algorithms, adding to the body of known efficient NO algorithms. Towards the end of this talk I will give a brief overview of some of my recent work related to computational sciences. First I will talk about "Pochoir" (pronounced "PO-shwar") - a stencil computation compiler for multicores developed at MIT CSAIL. Stencils have numerous applications in computational sciences including geophysics, fluid dynamics, finance, and computational biology. Next I will talk about "F2Dock" - a state-of-the-art rigid-body protein-protein docking software developed at UT Austin in collaboration with the SCRIPPS Research Institute. Docking algorithms have important applications in structure-based drug design, and in the study of molecular assemblies and protein-protein interactions