A B649 seminar will be offered in Spring 2003 at 2:30--3:45pm on Mondays and Wednesdays in LH019. Section 1361, 3 credits.
The subject is paradigms of programming for parallelism, specifically addressed to matrix problems, relating to my two research projects.
Beginning from the divide-and-conquer style implicit in functional programming, our goal is to attain superlative performance solving problems usual to the domain of high-performance computing. That is, we compete with fast programs on their terms.
While a superficial goal is high-performance, the real goal is to explore styles of programming that can achieve it from high-level programming. That is, while constraints of particular architectures (e.g. locality of reference) are acknowledged, the real goal is to program "around" particular constraints. Such styles have been called, ironically, both "cache oblivious" and "cache sensitive".
Such constraints include the memory hierarchy, balanced scheduling, synchronization of subprocesses, remote communication, pipelining, and access to standing libraries. Doubtless, not all of these will be beaten, but some of them will be dented. Perhaps, a new kind of algorithm might be uncovered.
It is a challenge for programming languages to eliminate such low-level concerns from high-level algorithms. One perspective on this seminar is how to embed support necessary to such a style into future compilers.
A challenge for high-performance and parallel computing is scheduling processes to run fast. Since a schedule depends on the data, another perspective is how data structures affect scheduling and performance.
To run new architectures fast we need to put the data close to the processing.
The starting points are suggested in the papers at and reference from http://www.cs.indiana.edu/~dswise/papers.html#quadtrees
Readings will be assigned from the literature---most of which are available from digital libraries to which IU already subscribes. (We can also discuss the survival of our computing archive in this era of digital libraries.)
Grading: Grading will be based on seminar participation and on a project. The project will involve implementation and testing of some algorithm(s). writing a term paper, and its formal presentation at the end of term.
Prerequisites: B503 or B515 or P536 or P573 or B581 or permission of instructor. In addition you should be able to program well in C, and know either Scheme, ML, or Haskell.
Research Assistantships: Two research assistantships are available beginning Spring Semester 2003 related to this material. These are funded under a new NSF ITR grant.
Office hours: to discuss, first, questions about the seminar and, second, the research assistantships are held in 330H Lindley, infromally during the week of January 6--10. Appointments via email.
====
David S. Wise +1(812)855-4866; fax: +1(812)855-4829 email
Computer Science Dept., Indiana University, Bloomington, IN 47405-7104, USA