Popular in Course
Popular in ComputerScienence
This 10 page Class Notes was uploaded by Roman McCullough on Friday October 30, 2015. The Class Notes belongs to CMPSCI 691 at University of Massachusetts taught by Staff in Fall. Since its upload, it has received 7 views. For similar materials see /class/232273/cmpsci-691-university-of-massachusetts in ComputerScienence at University of Massachusetts.
Reviews for S
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/30/15
Chapter 2 REGIONS AND THE ZPL LANGUAGE This chapter describes the ZPL language concentrating on the role of regions in its design To make this discussion both readable and precise some language concepts are introduced informally at rst and are then reconsidered with increased formality as the chapter progresses While this format would not be appropriate for a language reference manual it is designed to provide an appropriate mixture of clarity and precision for this presentation Note that this chapter focuses on the sequential interpretation of ZPL largely ignoring the parallel implications of regions and the language itself Since parallelism is inherent in the de nition and use of regions this will leave some questions unanswered at the chapter s conclusion These questions will be addressed in the following chapter which describes the parallel implications of regions This chapter s description of ZPL is meant to provide a general overview of the lan guage For a more complete description refer to the ZPL Programmer s Guide and the ZPL web page Sny99 ZPLOl The structure ofthis chapter is as follows Sections 21 2 14 describe the ZPL language including such fundamental concepts as regions arrays and array operators Section 215 illustrates ZPL s use in a number of small sample applications that will be used in subse quent chapters Section 216 describes other sequential approaches for array programming including vector indexing and slicing Finally Sections 217 and 218 provide an evaluation of ZPL s features in the sequential context listing both bene ts and liabilities of the region as it currently exists This chapter s contents serve as an expanded discussion of work that was published previously CLLS99 CLS99 21 ZPL s Guiding Principles Languages are for Communicating One of the primary principles that has guided ZPL s development is the notion that pro gram ming languages are meant to be a means of communication between human and computer Programmers have algorithms in their minds that they would like to execute on a computer Computers have nite resources and an extremely limited capacity for understanding high level languages Programming languages should form a bridge between these two points spanning the gap between programmer and computer using a direct natural route that com plements the abilities of both When this principle is violated communication is broken and a heroic effort is required by the user andor compiler if the program is to have its intended effect Such broken languages can result in macho compiling in which tremendous effort is put into helping a compiler recognize idioms that are not made apparent by the language and to implement them ef ciently These efforts tend to result in brittle optimizations that are easily broken if the programmer does not stick to the speci c set of idioms that the com piler recognizes Lew00 When the optimization does not re programmers must expend great effort to achieve their desired results Frustration abounds for both programmers and compiler implementors In contrast creating a language that is natural to compile to a given architecture allows implementors more time to work on general improvements and optimizations rather than worrying about particular syntactic patterns or corner cases It should be noted that most programming languages which have enjoyed widespread use have not relied on sophisti cated compiler optimizations to achieve acceptable baseline performance ZPL strives to implement this principle for parallel programming by providing a syntax that directly re ects parallelism This allows users to express the parallelism that is inherent in their algorithms and to evaluate the parallel overheads of their programs It also allows ZPL s implementors to detect parallelism trivially and create a straightforward baseline implementation By avoiding the 39 39 problem 39 can their 1 efforts on optimizations that improve the baseline implementation The False Seduction ofLegacy Code Reuse Many parallel computing approaches have been designed in hopes of taking advantage of existing sequential codes with minimal programmer effort For example a perfect par allelizing compiler would transform sequential programs into parallel code automatically Similarly languages such as High Performance Fortran HPF Hig94 and CoArray For tran CAF NR98 were designed with the idea of leveraging existing code as a primary goal Ideally programmers can take their existing sequential programs make minimal modi cations to them and end up with a good parallel implementation While this is a laudable goal the assumption that incremental changes can turn a good sequential algorithm into a good parallel one is naive The seductive pitch of these ap proaches is that the compiler will do all of the hard work for you once you add a line of code here or there to help it out The reality of the situation is that the work required to transform sequential programs into an optimal parallelizable form is often nontrivial for both the programmer and the compiler FJY 98 This effect is demonstrated by the con ceptual leap between the sequential and SUMNIA matrix multiplication implementations of Chapter 1 Often a parallel code bears little resemblance to its sequential counterpart In such cases the effort required to convert a sequential program into an effective parallel one can be greater than that which would have been required to write a new program from scratch with parallelism in mind Starting from First Principles ZPL approaches this problem from the opposite direction Rather than starting with a se quential language and striving to detect the parallelism inherent in its sequential syntax ZPL s design starts with nothing and incrementally adds concepts and operations that are Listing 21 Simple Type Constant and Variable Declarations in ZPL type age shortint coord record x integer y integer end constant pi double 314159265 tabsize integer 1000 maxage age 128 var done boolean length integer name string origin coord table array 1tabsize of complex implicitly parallel By starting from rst principles in this way ZPL was able to avoid supporting language constructs that disable parallelism As an example ZPL does not per mit traditional scalar indexing of its parallel arrays due to the fact that it is an inherently sequential construct This approach forces programmers to consider the opportunities for parallelism in a program from its inception rather than doing the minimal amount of work to get the compiler to accept their sequential code and then spending hours with feedback tools trying to determine why it is not achieving good parallel performance ZPL s syntax is based on ModulaZ Wir83 rather than a more popular language like C or Fortran This decision reinforces the idea of starting from scratch by forcing C and Fortran users to confront the notion that certain features of those languages are not present in ZPL due to their interference with parallelism eg pointers scalar array indexing and common blocks It also reinforces the idea that programmers should consider their se quential algorithms afresh when implementing them in parallel by making it dif cult for existing C and Fortran codes to be tweaked slightly and run through the compiler 30 Listing 22 Sample C c 39 Variable Declaration in ZPL config var n integer 100 if a sample problem size verbose boolean true if use to control output logn integer ngn 77 log of the problem size nsq integer nAZ if the problem size squared npi double pin if n times the constant pi A second reason for choosing Modula Z was to support a language whose syntax is both readable and intuitive While it would be possible to create C and Fortran dialects of ZPL no such effort has been made at this point The primary challenge would be to ensure that the features of C and Fortran which have been deliberately omitted from ZPL would interact appropriately with its parallel concepts or simply outlaw them altogether As Chapter 4 will discuss ZPL is compiled by translating it to C For this reason C s in uence is occasionally seen in the language s syntax For example the names of ZPL s data types and its formatting of IO both strongly re ect C 22 Scalar ZPL Concepts ZPL s scalar concepts are largely unoriginal and uninteresting but form an important foun dation for the rest of the language so are described here quite brie y 221 Data types Constants and Variables To start with the basics ZPL supports standard data types type declarations and declara tions for constants and variables as in most languages It supports integers of varying sizes as well as oating point and complex values of varying precision ZPL supports homoge neous array types referred to as indexed arrays and heterogeneous record types For some sample type constant and variable declarations refer to Listing 21 Table 21 A Summary of ZPL s Scalar Operators Arithmetic Operators Relational Operators Assignment Operators addition equality standard subtraction inequality accumulative multiplication lt less than subtractive division gt greater than multiplicative modulus lt less thanequal divisive exponentiation gt greater thanequal amp conjunctive I disjunctive Logical Operators Bitwise Operators amp and band and I or bor or not bnot complement bxor xor 222 Con guration Variables ZPL s con guration variables are a somewhat more unique scalar concept Each con g uration variable represents a loadtime constant a value that can be de ned at the outset of a program s execution but which cannot be changed thereafter This allows users to de ne values that they may not want to constrain at compile time such as problem sizes verbosity levels or tolerance values The advantage of making such values con guration variables rather than traditional variables is that it allows the compiler to treat the variable as a constant of unknown value during analysis and optimization Con guration variables are de ned similarly to normal constants except that their ini tializing values are merely defaults that can be overridden on the pro gram s commandline Con guration variable initializers may be de ned using expressions composed of constants scalar procedures and other con guration variables Currently ZPL only supports con g uration variables of scalar types including records and indexed arrays Listing 22 shows some sample con guration variable declarations 32 Listing 23 Sample Uses of ZPL s Control Structures if age gt maxage then write1nquotAge too largelquot end for i l to tabsize do tablei 0 end repeat length 2 done length lt 100 until done while originx gt originy do leftshiftorigin end 223 Scalar Operators ZPL supports a standard set of scalar arithmetic logical relational bitwise and assignment operators See Table 21 for an overview 224 Control Structures ZPL supports standard control structures such as conditionals for loops while loops and repeatuntil loops See Listing 23 for some simple examples 225 Blank Array References To encourage arraybased thinking ZPL s indexed arrays support a shorthand notation to operate over their entire index range without a loop This is done by omitting the indexing expression for an array reference For example the assignment to table in Listing 23 could be written as follows using blank array references table 0 Listing 24 Sample ZPL Procedures prototype mycompx double y double integer procedure leftshiftvar pt coord begin ptx 10 end procedure mycompx double y double integer begin if x lt y then elsif x y then return 0 else return 1 This syntactic shortcut is designed to aid With the common case of performing purely ele mentWise operations on indexed arrays In many codes blank array references can elimi nate a number of trivial and uninteresting loops over an array s indices 226 Procedures ZPL s primary functional unit is the procedure Which can accept value or reference pa rameters and return a single value of arbitrary type Procedures strongly resemble their Modula 2 counteIparts and may be recursive ZPL also supports prototypes that allow a procedure s signature to be declared for use before the procedure is de ned Listing 24 contains some sample prototype and procedure de nitions 227 Interfacing with External Code Though ZPL s choice of Modula 2 as a base syntax limits the amount of code reuse that can take place Within the parallel portion of a ZPL program existing scalar code can be 34 Listing 25 An Example of Using extern in ZPL extern constant MPI double extern var errno integer extern type timezone opaque timeval record tvsec longint tvusec longint end extern prototype gettimeofdayvar tv timeval var t2 timezone integrated into a ZPL program if it can be called by and linked into a C program This is achieved using the extern keyword which can be applied to types constants valiables and procedures Exteinal types may be partially speci ed or omitted completely using the opaque keyword which allows the programmer to store vaIiables of exte1nal types and pass them around but not to operate on them directly or modify them See Listing 25 for some sample exte1nal declarations 23 Regions and Parallel Arrays As mentioned in the introduction ZPL s fundamental concept is that of the region A region is simply an index set a set of indices in a coordinate space of arbitrary dimensions ZPL s regions are regular and rectilinear in nature In this sense they are much like traditional alrays with no associated data This similality is emphasized syntactically simple regions are de ned using syntax that resembles a traditional array s bounds For example the following shows a simple twodimensional region and the set of indices that it desc1ibes 1 m l n 1l121n21m71 Regions may contain singleton dimensions which descIibe only a single index value These are de ned by replacing the degenerate range with a single index eg l l 11 rather thanll ln
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'