Since 2008, NSF and The College Board, have been developing a "Computer Science: Principles" curriculum to "introduce students to the central ideas of computing and CS, to instill ideas and practices of computational thinking, and to have students engage in activities that show how computing and CS change the world". We report on the initial pilot of the CS Principles curriculum at 5 universities in 2010/11. The instructors from the pilot schools will describe their classes, the piloting experience (teaching under a microscope), and successes and failures. Emphasis will be on: mapping the CS Principles curriculum to a college's specific needs, and how others can use or modify the existing materials for pilots at their schools.

Since APL, reductions and scans have been recognized as powerful programming concepts. Abstracting an accumulation loop (reduction) and an update loop (scan), the concepts have efficient parallel implementations based on the parallel prefix algorithm. They are often included in high-level languages with a built-in set of operators such as sum, product, min, etc. MPI provides library routines for reductions that account for nearly nine percent of all MPI calls in the NAS Parallel Benchmarks (NPB) version 3.2. Some researchers have even advocated reductions and scans as the principal tool for parallel algorithm design.Also since APL, the idea of applying the reduction control structure to a user-defined operator has been proposed, and several implementations (some parallel) have been reported. This paper presents the first global-view formulation of user-defined scans and an improved global-view formulation of user-defined reductions, demonstrating them in the context of the Chapel programming language. Further, these formulations are extended to a message passing context (MPI), thus transferring global-view abstractions to local-view languages and perhaps signaling a way to enhance local-view languages incrementally. Finally, examples are presented showing global-view user-defined reductions "cleaning up" and/or "speeding up" portions of two NAS benchmarks, IS and MG. In consequence, these generalized reduction and scan abstractions make the full power of the parallel prefix technique available to both global- and local-view parallel programming.

No abstract available.

Gather and scatter are data redistribution functions of longstanding importance to high performance computing. In this paper, we present a highly-general array operator with powerful gather and scatter capabilities unmatched by other array languages. We discuss an efficient parallel implementation, introducing three new optimizations—schedule compression, dead array reuse, and direct communication—that reduce the costs associated with the operator’s wide applicability. In our implementation of this operator in ZPL, we demonstrate performance comparable to the hand-coded Fortran + MPI versions of the NAS FT and CG benchmarks. Categories and Subject Descriptors D.3.2 [Programming Languages]: Language Classifications—concurrent, distributed and parallel languages

This paper describes an array-based language-level approach to parallel sparse computation. Our approach is unique due to its separation of sparse index sets from arrays, both syntactically and in the implementation. This design allows users to express their computation using dense array syntax, making the code easier for readers to understand and for compilers to parallelize and optimize. This work is done within the context of Advanced ZPL, retaining its crisp syntax and source-level performance model. Our implementation uses a novel sparse storage format that supports general operations such as arbitrary iteration and slicing. We describe how our compiler automatically optimizes this data structure in to more compact forms based on the operations required by the program. We demonstrate our approach using the NAS CG and MG benchmarks, comparing our implementations with the original Fortran+MPI versions in terms of clarity and performance. We present performance results on the Cray T3E indicating that our implementation compares favorably to the hand-coded NAS versions in terms of memory requirements and often surpasses them in terms of execution speed.

Array programming languages such as Fortran 90, High Performance Fortran and ZPL are well-suited to scientific computing because they free the scientist from the responsibility of managing burdensome low-level details that complicate programming in languages like C and Fortran 77. However, these burdensome details are critical to performance, thus necessitating aggressive compilation techniques for their optimization. In this paper, we present a new compiler optimization called Array Subexpression Elimination (ASE) that lets a programmer take advantage of the expressibility afforded by array languages and achieve enviable portability and performance. We design a set of micro-benchmarks that model an important class of computations known as stencils and we report on our implementation of this optimization in the context of this micro-benchmark suite. Our results include a 125% improvement on one of these benchmarks and a 50% average speedup across the suite. Also we show a speedup of 32% improvement on the ZPL port of the NAS MG Parallel Benchmark and a 29% speedup over the hand-optimized Fortran version. Further, the compilation time is only negligibly affected.

Hierarchical algorithms such as multigrid applications form an important cornerstone for scientific computing. In this study, we take a first step toward evaluating parallel language support for hierarchical applications by comparing implementations of the NAS MG benchmark in several parallel programming languages: Co-Array Fortran, High Performance Fortran, Single Assignment C, and ZPL. We evaluate each language in terms of its portability, its performance, and its ability to express the algorithm clearly and concisely. Experimental platforms include the Cray T3E, IBM SP, SGI Origin, Sun Enterprise 5500, and a high-performance Linux cluster. Our findings indicate that while it is possible to achieve good portability, performance, and expressiveness, most languages currently fall short in at least one of these areas. We find a strong correlation between expressiveness and a language’s support for a global view of computation, and we identify key factors for achieving portable performance in multigrid applications.

The goal of producing architecture-independent parallel programs is complicated by the competing need for high performance. The ZPL programming language achieves both goals by building upon an abstract parallel machine and by providing programming constructs that allow the programmer to "see" this underlying machine. This paper describes ZPL and provides a comprehensive evaluation of the language with respect to its goals of performance, portability, and programming convenience. In particular, we describe ZPt's machine-independent performance model, describe the programming benefits of ZPL's region-based constructs, summarize the compilation benefits of the language's high-level semantics, and summarize empirical evidence that ZPL has achieved both high performance and portability on diverse machines such as the IBM SP-2, Cray T3E, and SGI Power Challenge.

In this paper we describe a parallelprogrammingparadigm called problem space promotion (PSP), a technique that increases parallelism by reducing communication and synchronization.We present four algorithms that exploit PSP and evaluate their communication characteristics relative non-PSP solutions.Our analysis is aided by the use ofparallel algorithm notation that is concise, yet accurately reflects parallelism and communication costs.Our analysis illustrates circumstances under which the use of PSP is benejcial and detrimental to performance, and experiments on the Cray T3E attest to the validity of the analysis.We find that PSP can signtficantly improve the per$ormance and scaling behavior of certain computations, even when compared to existing high quality parallel algorithms.

ZPL is a parallel array language designed for high performance scientific and engineering computations. Unlike other parallel languages, ZPL is founded on a machine model (the CTA) that accurately abstracts contemporary MIMD parallel computers. This makes it possible to correlate ZPL programs with machine behavior. As a result, programmers can reason about how code will perform on a typical parallel machine and thereby make informed decisions between alternative programming solutions. The paper describes ZPL's performance model and its syntactic cues for conveying operation cost. The what you see is what you get (WYSIWYG) nature of ZPL operations is demonstrated on the IBM SP-2, Intel Paragon, SGI Power Challenge, and Cray T3E. Additionally, the model is used to evaluate two algorithms for matrix multiplication. Experiments show that the performance model correctly predicts the faster solution on all four platforms for a range of problem sizes.

Array languages such as Fortran 90, HPF and ZPL have many benefits in simplifying array-based computations and expressing data parallelism. However, they can suffer large performance penalties because they introduce intermediate arrays---both at the source level and during the compilation process---which increase memory usage and pollute the cache. Most compilers address this problem by simply scalarizing the array language and relying on a scalar language compiler to perform loop fusion and array contraction. We instead show that there are advantages to performing a form of loop fusion and array contraction at the array level. This paper describes this approach and explains its advantages. Experimental results show that our scheme typically yields runtime improvements of greater than 20% and sometimes up to 400%. In addition, it yields superior memory use when compared against commercial compilers and exhibits comparable memory use when compared with scalar languages. We also explore the interaction between these transformations and communication optimizations.

In parallel programming, the need to manage communication, load imbalance, and irregularities in the computation puts substantial demands on the programmer. Key properties of the architecture, such as the number of processors and the cost of communication, must be exploited to achieve good performance, but coding these properties directly into a program compromises the portability and flexibility of the code because significant changes are then needed to port or enhance the program. We describe a parallel programming model that supports the concise, independent description of key aspects of a parallel program-including data distribution, communication, and boundary conditions-without reference to machine idiosyncrasies. The independence of such components improves portability by allowing the components of a program to be tuned independently, and encourages reuse by supporting the composition of existing components. The isolation of architecture-sensitive aspects of a computation simplifies the task of porting programs to new platforms. Moreover, the model is effective in exploiting both data parallelism and functional parallelism. This paper provides programming examples, compares this work to related languages, and presents performance results.

Using a specially constructed machine independent communication optimizer that allows control over optimization selection, we quantify the performance benefit of three well known communication optimizations: redundant communication removal, communication combination, and communication pipelining. The numbers are shown relative to the base performance of benchmark programs using the standard communication optimization of message vectorization. The effects on the number of calls to communication routines, both static and dynamic, are tabulated. We consider a variety of communication primitives including those found in Intel's NX library, PVM and the T3D's SHMEM library. The results show substantial improvement, with two combinations of optimizations being most effective.

A portable program executes on different platforms and yields consistent performance. With the focus on portability, this paper presents an in-depth study of the performance of three NAS benchmarks (EP, MG, FT) compiled with three commercial HPF compilers (APR, PGI, IBM) on the IBM SP2. Each benchmark is evaluated in two versions: using DO loops and using F90 constructs and/or HPF's Forall statement. Base-line comparison is provided by versions of the benchmarks written in Fortran/MPI and ZPL, a data parallel language developed at the University of Washington.While some F90/Forall programs achieve scalable performance with some compilers, the results indicate a considerable portability problem in HPF programs. Two sources for the problem are identified. First, Fortran's semantics require extensive analysis and optimization to arrive at a parallel program; therefore relying on the compiler's capability alone leads to unpredictable performance. Second, the wide differences in the parallelization strategies used by each compiler may require an HPF program to be customized for the particular compiler. While improving compiler optimizations may help to reduce some performance variations, the results suggest that the foremost criteria for portability is a concise performance model that the compiler must adhere to and that the users can rely on.

Routers that provide a single kind or class of routing have been thoroughlystudied, and much is known about their favorable and unfavorable properties.For example, oblivious routers are simple and deliver messages in-order, but they have lower throughput when the network is congested.Adaptive routers are more complex, can deliver messages out-of-order, but have better throughput characteristics.No one router is perfect.This paper investigates the idea of routing with multiple kinds of traffic simultaneously.We call such routers multi-class routers.The approach is not to group three independent routers together on a chip, but rather to create an integrated multi-class router capable of simukmeously processing messages for each of the classes supported.Clearly, deadlock and livelock are critical issues with multiple claases, since traflic from one claas must not cause deadlock in another.Triplex is the first triple class router.It supports oblivious, minimaJ fully adaptive, and non-minimal fully adaptive routing classes for k-ary n-cubes.Alternatives can be chosen at boot-time, or per message.Triplex is suitable for wormhole or packet flow control and is shown to be deadlock-free and livelock-free.One figure of merit for evaluating multiclaas routers is the performance penalty over each of the best single class routers.Triplex is competitive with the best oblivious and the best minimal fully adaptive router, but on this metric is inferior to the best non-minimal fully adaptive router.An open question posed by this research is whether there exists a triple class router that is competitive for all three classes of routing.lliplex is also of independent interest, since it is the first non-minimal fully adaptive deadlock avoidance wormhole algorithm for tori.

Chaotic routers are randomizing, nonminimal adaptive packet routers designed for use in the communication networks of parallel computers. Chaotic routers combine the flexibility found in adaptive routing with a design simple enough to be competitive with the most streamlined oblivious routers. We review chaotic routing and compare it with other contemporary network routing approaches, including state-of-the-art oblivious and adaptive routers. A detailed head-to-head comparison between oblivious, minimal adaptive, and chaotic routing is then presented, exploring the performance of comparable VLSI implementations through analysis and simulation. The results indicate that chaotic routers provide very effective and efficient high-performance message routing.

The Chaos router, a randomizing, nonminimal adaptive packet router is introduced. Adaptive routers allow messages to dynamically select paths, depending on network traffic, and bypass congested nodes. This flexibility contrasts with oblivious packet routers where the path of a packet is statically determined at the source node. A key advancement of the Chaos router over previous nonminimal routers is the use of randomization to eliminate the need for livelock protection. This simplifies adaptive routing to be of approximately the same complexity along the critical decision path as an oblivious router. The primary cost is that the Chaos router is probabilistically livelock free rather than being deterministically livelock free, but evidence is presented implying that these are equivalent in practice. The principal advantage is excellent performance for nonuniform traffic patterns. The Chaos router is described, it is shown to be deadlock free and probabilistically livelock free, and performance results are presented for a variety of work loads.>

The Chaos router is an adaptive, randomized message router for multlicomputers.Aclaptive routers are superior to oblivious routers, the state-of-the-art, because they can by-pass congestion and faults.unlike other adaptive routers, however, the Chaos router has reduced the complexity along the critical path of the routing decision by using randomization to eliminate livelock protection, The foundational theory for Chaotic routing, proving that, this approach is sound, has been previously de~-eloped [1 1].In this paper we present, the complete design of the router together with (simulated) performance figures.The results show that, the Chaos t-outer is competitive with the simple and fast obli~ious routers for random loads and greatly superior for loads with hot spots. 1 Non-nliuimal, adaptive routers, as shown by our simulat ions, have the potential of outperforming minimal, adaptive routers, especially under non-uniform traffic.Their disad~ant,age though is their difficulty in guarant wing freedom from ltrc lock.L,6.guarantee that, no message will fail to be deli~"ered because it is repeatedly derout ed.The well known solution to this problem is priorit ~-routing, where messages are assigned a timestamp upon injection into the network.JYhen multiple messages require the same channel the oldest one is selected.Priority routing is known to be expensive, not only because it increases the message length in order to incorporate the timestamp, but, even more so because

Four algorithms are analyzed in the shared and nonshared (distributed) memory models of parallel computation. The analysis shows that the shared memory model predicts optimality for algorithms and programming styles that cannot be realized on any physical parallel computers. Programs based on these techniques are inferior to programs written in the nonshared memory model. The unit cost charged for a reference to shared memory is argued to be the source of the shared memory model's inaccuracy. The implications of these observations are discussed.>

We introduce a performance metric, normalized time, which is closely related to such measures as the area-time product of VLSI theory and the price / performance ratio of advertising literature. This metric captures the idea of a piece of hardware “pulling its own weight,” i.e. contributing as much to performance as it costs in resources. We then prove general theorems for stating when the size of a given part is in balance with its utilization, and give specific formulas for commonly found linear and quadratic devices. We also apply these formulas to an analysis of a specific processor element, and discuss the implications for bit-serial vs word-parallel, RISC vs CISC, and VLIW designs.

It is shown how a communication abstraction called the port ensemble can simplify the handling of boundary conditions and the efficient porting of programs. A port ensemble provides an explicit interface between computation and communication descriptions, thus separating the communication structure from the details of local computation and from the compiler. Port ensembles structure ports, symbolic names to and from which process can write and read values. To simplify the expression of boundary conditions, ports can be bound not only to ports on other processors, but also to nonexistent neighbors (along the edge of the computation) using special objects that represent and implement constants, variables, and arbitrary functions. Port ensembles also provide direct access to the communication structure, which simplifies changing the structure to one appropriate for a new target architecture.>

We present the chaos router, an asynchronous adaptive router, which under certain circumstances can send messages farther from their destinations.The chaos router greatly simplifies the routing logic by removing the livelock protection of previous schemes.Through an effective use of randomness, whose sources include that due to the adaptively processed load, the natural timing differences of selftimed circuitry and explicitly injected randomization, the chaos router avoids long message routes with high probability.In this paper the router is described, it is argued that the chaos router is deadlock free and probabilistically livelock and starvation free, and simulation results are presented showing that the chaos router performs well.

The authors apply a formal model described by M.L. Bailey and L. Snyder (Distributed Simulation, SCS, 1989, p.157-63) to the more difficult problem of comparing three different synchronization strategies: synchronous, conservative asynchronous, and optimistic asynchronous. They show that with unlimited processors, for variable-delay and unit-delay timing, conservative>

Conversion algorithms are presented that would enable programmers to write programs in a high-level, data flow language and then run those programs on a synchronous machine. A model of interprocess communication systems is developed in which both data-driven and synchronous execution modes are represented. Balancing equations are used to characterize a subclass of parallel programs, called loop programs, for which conversions are possible. We show that all loop programs having the finite buffer property can be converted into synchronous mode. Finally two algorithms for the conversion of loop programs are presented and discussed.

The Pringle is a 64 processor MIMD computer with a 64 M (8 bit) instructions per second execution rate. (Copies are running at Purdue and Washington.) The Pringle runs programs written for the Configurable, Highly Parallel (CHiP) Computer. That is, the Pringle executes the 64 separate instruction streams as well as the interconnection (phase) stream that configures the lattice of a 64 processor CHiP computer. But the Pringle is not a CHiP. It gives the illusion of the CHiP machine's conflict-free, point-to-point communication using a 64 Mbit internal polled bus. In addition to describing the design goals and the Pringle architecture, this paper identifies two problems common to novel architecture implementation projects, the “wisdom of experience” problem and the “single instance” problem, and expalins how they were addressed for the Pringle.

A collection of parallel processors is said to be coordinated if each write from one processing element (PE) to another is answered by a read. We report on an efficient algorithm to test coordination for parallel programs in which the code for each PE is a loop. We also test a weaker predicate for parallel algorithms with oblivious PE codes and we show that the general problem is PSPACE-hard.

We present algorithms that convert a class of parallel programs, called loop programs, from data-driven mode to synchronous mode. Such algorithms enable programmers to use a high-level, data-driven programming language without forfeiting the efficiency of a synchronous machine. We characterize loop programs for which conversion is possible in terms of sets of balancing equations and we present two conversion algorithms.

Information is not transferred instantaneously; there is always a propagation delay before an output is available as an input to the next computational step. Propagation delay is a function of wire length, so we study the length of edges in planar graphs. We prove matching (to within a constant factor) upper and lower bounds on minimax edge length for four planar embedding problems for complete binary trees. (The results are summarized in Table 1.) Because trees are often subcircuits of larger circuits, these results imply general performance limits due to propagation delay. The results give important information for the popular technique of pipelining.

The role of formal modeling in the study of capability- based protection systems is explained. Historical background is presented and a model of a computer science department's computer system is presented. A survey of several important capability-based models is given including the Harrison, Ruzzo, Ullman model, the Take-Grant model, and grammatical models. These models are presented in a unified manner with consistent terminology. The main results of the models are given. These results are compared, contrasted, and interpreted in the context of numerous examples.

A B-tree is compact if it is minimal in number of nodes, hence has optimal space utilization, among equally capacious B-trees of the same order. The space utilization of compact B-trees is analyzed and compared with that of noncompact B-trees and with (node)-visit-optimal B-trees, which minimize the expected number of nodes visited per key access. Compact B-trees can be as much as a factor of 2.5 more space efficient than visit-optimal B-trees; and the node-visit cost of a compact tree is never more than 1 + the node-visit cost of an optimal tree. The utility of initializing a B-tree to be compact (which initialization can be done in time linear in the number of keys if the keys are presorted) is demonstrated by comparing the space utilization of a compact tree that has been augmented by random insertions with that of a tree that has been grown entirely by random insertions. Even after increasing the number of keys by a modest amount, the effects of compact initialization are still felt. Once the tree has grown so large that these effects are no longer discernible, the tree can be expeditiously compacted in place using an algorithm presented here; and the benefits of compactness resume.

Problems concerned with finding inscribing or circumscribing polygons that maximize some measurement are considered such as: Find an area maximizing triangle inscribed in a given convex polygon. Algorithms solving a number of these problems in linear time are presented. They use the common approach of finding an initial solution with respect to a fixed bounding point and then iteratively transforming this solution into a new solution with respect to a new point. The generality of this approach is discussed and several open problems are noted.

A B-tree is compact if it is minimal in number of nodes, hence has optimal space utilization, among equally capacious B-trees of the same order. The space utilization of compact B-trees is analyzed and is compared with that of noncompact B-trees and of (node)-visit-optimal B-trees, which minimize the expected number of nodes visited per key access. Compact B-trees can be as much as a factor of 2.5 more space-efficient than visit-optimal B-trees; and the node-visit cost of a compact tree is never more than 1 + the node-visit cost of an optimal tree. Finally, an in-place compactification algorithm is presented which operates in linear time in the size of the file.

In the context of a capability-based protection system, the term “transfer” is used (here) to refer to the situation where a user receives information when he does not initially have a direct “right” to it. Two transfer methods are identified: de jure transfer refers to the case when the user acquires the direct authority to read the information; de facto transfer refers to the case when the user acquires the information (usually in the form of a copy and with the assistance of others), without necessarily being able to get the direct authority to read the information. The Take-Grant Protection Model, which already models de jure transfers, is extended with four rewriting rules to model de facto transfer. The configurations under which de facto transfer can arise are characterized. Considerable motivational discussion is included.

The 2,3-trees that are optimal in the sense of having minimal expected number of nodes visited per access are characterized in terms of their “profiles”. The characterization leads directly to a linear-time algorithm for constructing a K-key optimal 2,3-tree for a sorted list of K keys. A number of results are derived that demonstrate how different in structure these optimal 2,3-trees are from their “average” cousins.

Those 2,3-trees that are minimal in expected number of comparisons per access for a given number of keys are characterized. The characterization yields directly a linear-time algorithm for constructing a minimal-comparison 2,3-tree for a given sorted set of keys. Regrettably, the property of comparison minimality is incompatible with the earlier-studied property of node-visit optimality. Specifically, the two types of optimality can coexist in a K-key 2,3-tree only for sixteen values of K, none exceeding 32. In contrast, comparison-minimal node-visit-pessimalK-key 2,3-trees exist for just over half the possible values of K.

A model for searching algorithms is developed which includes most tree-like searching structures such as lists, binary trees, AVL trees and 2, 3-trees. It is shown that no searching algorithm employing a data structure that is uniquely represented (up to isomorphism) can provide search, insert and delete functions all operating faster than c√n time for every n key tree. The c√n bound is shown to be achievable for uniquely represented data structures.

A particular protection mechanism from the protection hterature-the take and grant system--is presented For this particular mechanism, it is shown that the safety problem can be solved in linear time Moreover the security policies that this mechanism can enforce are characterized KEY WORDS AND PHRASES protection,

The Folklore is replete with stories of "secure" protection systems being compromised in a matter of hours. This is quite astounding since one is not likely to claim that a system is secure without some sort of proof to support the claim. In practice, proof is not provided and one reason for this is clear: although the protection primitives are apparently quite simple, they may potentially interact in extremely complex ways. Vague and informal arguments, therefore, often overlook subtleties that an adversary can exploit. Precision is not merely desirable for protection systems, it is mandatory.

A model is defined in which questions concerning delay bounded asynchronous parallel systems may be investigated. Persistence and determinacy are introduced for this model. These two conditions are shown to be sufficient to guarantee that a synchronous execution policy can be relaxed to an asynchronous execution policy with no change to the result of the computation. In addition, the asynchronous execution time is only (D+1) times the synchronous execution time, where D is the delay bound. A wide class of recognition problems is identified which can be solved by linear asynchronous structures. Also, it is shown that synchronization problems, similar to the "firing squad synchronization problem," cannot be solved by delay bounded asynchronous systems.