The Taub Faculty of Computer Science Events and Talks

In this talk I will describe the algorithms and mechanisms underlying a distributed system for genetic linkage analysis, called Superlink-online. It is a production online system which serves hundreds of geneticists worldwide allowing for faster analysis of genetic data via automatic parallelization and execution on thousands of non-dedicated computers. I will describe the following innovative technologies forming the core of this system 1. Practical scheduling and execution of embarrassingly parallel Bags of Tasks in multiple non-dedicated computing environments (SC09). Our approach allows for virtualization of multiple grids, clouds and volunteer grids as a single computing platform by building an overlay of execution clients over the physical resources; another component is a generic mechanism for dynamic scheduling policies to reduce the turnaround time in the presence of resource failures and heterogeneity. Our system has executed hundreds of Bags of Tasks with over 9 million jobs during 3 months alone; these have been invoked on 25,000 hosts from the local clusters, the Open Science Grid, EGEE, UW Madison pool and Superlink@Technion community grid. 2. A general technique for designing memory-bound algorithms on GPUs through software-managed cache (ICS08). This technique was successfully applied to the probabilistic network inference yielding an order of magnitude performance improvement versus the performance without such a cache. Overall we achieved up to three orders of magnitude speedup when executing our GPU-based algorithm versus single CPU performance. 3. Coarse- and fine-grained parallel algorithms for the inference in probabilistic networks on large-scale non-dedicated environments and GPUs. We devised and implemented an algorithm suitable for loosly coupled environments with unreliable resources (American Journal of Human Genetics 2006, HPDC06) and adapted it for heterogeneous GPU-CPU supercomputer TSUBAME in Tokyo Institute of Technology.