How Good Can Parallel Algorithms Really Be?

University Of Maryland, College Park, College Park MD

Investigators

Abstract

Institution: U of MD College Park Proposal Number: CCR-9988256 How Good Can Parallel Algorithms Really Be? Uzi Vishkin, PI and Manoj Franklin, co-PI Abstract Experimental study of parallel algorithms and applications is proposed. The investigators plan to conduct this study with respect to the Explicit Multi-Threaded (XMT) platform for instruction-level parallelism (ILP). A general goal of this work is to promote \thinking and programming in parallel". For this the investigators will try to better understand the performance potential of a platform such as XMT relative to existing parallel and serial platforms/models. Work which the investigators have already done provides interesting preliminary examples for mixing experimental research and theoretical analysis. This preliminary work appears to update previous knowledge by suggesting that: (i) Good speedups for much smaller inputs are possible. (ii) Incorporating analytic (non-asymptotic) performance evaluation into experimental performance analysis is possible; this includes applicability to relatively small inputs. Explicit Multi-Threading (XMT) is a fine-grained computation framework introduced in a SPAA'98 paper by Vicki et al. XMT aims at faster single-task completion time by way of ILP. Building on some key ideas of parallel computing, XMT covers the spectrum from algorithms through architecture to implementation; the main implementation related innovation in XMT is through the incorporation of low-overhead hardware and software mechanisms (for more effective fine-grained parallelism).