EE392C: Advanced Topics in Computer Architecture Lecture #9Polymorphic ProcessorsStanford University Tuesday, May 6, 2003Programming ModelsLecture #9: Tuesday, 29 April 2003Lecturer: Paul W. Lee, Rebecca Schultz, Varun S. MalhotraScribe: Sorav Bansal, Brad Schumitsch1 Introductio nThe need for a simple, correct and general programming model cannot be over-emphasized.A good programming model is instrumental in mapping the parallelism in the applicationto the suppo r t f or parallelism in the hardware. There are two perspectives to keep inmind when designing a programming model - the perspective of the progr ammer and theperspective of the compiler-writer.From the point of view of the programmer1. The interface should be easy and intuitive2. The model should make it easy for the progr ammer to identify parallelism andindicate it. The complexity should be hidden by the compiler.3. The progra mming model should be architecture-independent4. The progra mmer should not need to worry about details like locality-of-usage.From the point of view of the Compiler-WriterThe program structure should convey some parallelism that the compiler can exploit.This parallelism could be either ILP, TLP or ILP. Present-day programming languageslike C hide everything but ILP.The papers we discussed ([1], [2], [3]) present three different approaches to progra m-ming model design.2 Paper Su mmaries2.1 Container-Centric Approach For Parallelizing Applications([1])Parallelizing compilers have been successful in arr ay based numerical applications, butthe success has been limited in other areas. To effectively para llelize applications for2 EE392C: Lecture #9Parallelismin ApplicationProgrammingModelSupport forParallelismin Hardwarethese other areas, the compiler should be aware o f the attributes of a program in termsof its aggregate data structures.This paper presents the concept of containers, a ny general-purpose ag gregate dat atype such as matrices, lists, tables, graphs and I/O streams. The use of containers isvery similar in most programs independent of implementation, and can be abstractedfor use in data analysis and parallelization. The paper uses two of the most commoncontainers to demonstrate its ideas. Linear containers are containers where its elementsare accessed in a linear manner, such as lists, stacks and queues. Content-addressablecontainer elements are accessed through keys. Examples of this are tables, sets, andmaps.Containers are central to the flow of data, and are a primary source of data parallelism,but conventional compilers are not awa re of the structure of containers and thus cannottake advantage of the information at this level. In order to describe concrete containers tothe compiler, the paper introduces abstract containers and methods. The compiler takesas input, in addition to the source code, the container description in terms of abstractcontainers, to perform container specific analysis and transformation to parallelize theprogram.The paper discusses container-based transformation techniques such as loop paral-lelization, container privatization, and exploiting associativity. All of these transforma-tions are analogous to similar transformations on arrays. Dependency test methods arealso explored. Range checks are used for linear containers, and commutativity analysisis used for content-addressable containers. Disjoint keys result in commutativity, butoverlapping keys are very difficult to analyze. The pattern search-otherwise insert issuggested as a possible commutative case.A number of Java, C++, a nd C applications were studied to identify possible trans-formation techniques. The applications were manually parallelized using the above-mentioned techniques, and large parts of the applications could be parallelized. Thepaper unfortunately does not give any results to indicate how effective these transforma-tions were in terms of performance improvement.The paper prop oses using the information at the data structure level to parallelizeprograms. The widespread use of containers such as C++ STL makes this approachvery attractive as a way to attain higher levels of parallelization without burdening theprogrammer. The notion of abstract containers is useful as a specification language forEE392C: Lecture #9 3containers, and provides a starting point in using this approach in automatic paralleliza-tion. The informatio n from containers could be useful in other ways as well. It can beused for more efficient data placement or prefetching, for example.2.2 Coarse Grain Parallel Programming in Jade ([2])Upcoming architectures have different support for exploiting different forms o f parallelism(ILP, DLP, TLP) in the applications. There is need for good programming models thatcan map the parallelism inherent in the progra ms efficiently onto these architecturesto leverage maximum benefits. Efforts in this area have been directed at (1) comingup with restrictive programming models which cater to a subset of applications andmapping them well onto the underlying architectures, and (2) new programming modelswherein programmer gives information to the compiler and the underlying runtime systemimplicitely or explicitely helping them to exploit parallelism. This paper introduces onesuch scheme wherein programmer provides information to the compiler explicitely byspecifying the data usage patterns in the program.Traditionally programmers have been writting programs for parallel machines usingexplicitely parallel languages. However, programmers using one of t he explicit parallellanguages have to directly implement program’s global concurrency using low constructsto create parallel tasks a nd explicit connections between these parallel tasks. Although,explicit parallel languages give programmer maximum control over the parallel executionwhich can be exploited to generate extremely efficient parallel programs, but it putsthe burden on the programmers to manage many of the low level aspects associatedwith mapping of computation onto the parallel machine. Another pro blem with theseexplicitely parallel languages is that it is difficult to port a program written for onemachine to another machine with a substantially different progra mming interface.This paper presents Jade, a la nguage which has provision for expressing coar se grainparallelism while sticking t o the sequential programming paradigm. Jade is data-orientedlanguage for parallelizing programs written in a serial, imperative