English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Object-oriented techniques have been pro ered as aids for managing complexity, enhancing reuse, and improving readability of irregular parallel applications. However, as performance is the major reason for employing parallelism, programmability and high performance must be delivered together. Using a suite of seven challenging irregular applications and the mature Illinois Concert system (a high-level concurrent object-oriented programming model backed by an aggressive implementation), we evaluate what programming e orts are required to achieve high performance. For all seven applications, we achieve performance comparable to the best reported for low-level programming means on large-scale parallel systems. In general, a high-level concurrent object-oriented programming model supported by aggressive implementation techniques can eliminate programmer management of many concerns { procedure and computation granularity, namespace management, and low-level concurrency management. Our study indicates that these concerns are fully automated for these applications. Decoupling these concerns makes managing the remaining fundamental concerns { data locality and load balance { much easier. In several cases, data locality and load balance for the complex algorithm and pointer data structures is automatically managed by the compiler and runtime, but in general programmer intervention was required. In a few cases, more detailed control is required, speci cally explicit task priority, data consistency, and task placement. Our system integrates the expression of such information cleanly into the programming interface. Finally, only small changes to the sequential code were required to express concurrency and performance optimizations, less than 5% of the source code lines were changed in all cases. This bodes well for supporting both sequential and parallel performance in a single code base. keywords: conncurent object-oriented programming, high-level parallel models 1 Overview Object-oriented techniques have been pro ered as aids for managing complexity, enhancing reuse, and improving readability of parallel applications. Numerous variants have been explored (e.g. [40]) with a great volume of technical papers published. Concurrent object systems appear particularly promising for irregular applications where modularity and encapsulation help manage the complex data and parallelism structures. In this paper, we systematically evaluate a high level concurrent object system's programmability for achieving high performance on irregular applications. While signi cant bodies of research exist for both implementing irregular parallel applications e ciently and concurrent object-oriented programming, we know of no studies that addresses both together. While there is a wealth of other research on programming irregular parallel applications, none of these approaches provide a single programming interface while supporting all three dimensions of irregularity { data, control, and concurrency. Research e orts have largely focused on building special libraries which provide runtime support for one or several dimensions of irregularity. For example, the inspector-executor approach uses a library to support iterated irregular communication (such as in nite element simulations) [19]. The 2 Multipol library provides a set of tools to build irregular applications, but no uniform high level interface [39]. Libraries such as Sparspak, Kelp, and A++/P++ support particular classes of algorithms on sparse matrices and adaptive meshes [11, 27]. Of the many concurrent object-oriented programming systems, nearly all have chosen to ignore support for ne-grained parallelism. This greatly complicates the task of programming irregular applications by forcing programmers to map irregular concurrency into grains large enough to achieve e ciency. For example, systems such as pC++ [24], CC++ [7] (these two languages have been combined into HPC++), and Mentat [16] (now a basis for the Legion project) all use heavyweight threads. Of the few systems which have explored ne-grained concurrency (ABCL/f [43], MPC++, and the Illinois Concert system), this study is the rst systematic evaluation of programming e ort for a signi cant range of irregular applications. Our application study is done in the context of the Illinois Concert system, a high performance compiler and runtime for parallel computers which has been the vehicle for extensive research on compiler optimization and runtime techniques over the past ve years [9, 32, 29, 30, 33, 28, 31, 12, 44, 23, 22]. While no system contains all known optimizations, the Concert system contains a wide range of aggressive optimizations, and has been used to demonstrate high performance in absolute terms on a wide range of applications [23, 45, 10]. In e ect, the Concert system automatically addresses many of the concerns which programmers explicitly manage in lower level programming models (e.g. explicit threads or message passing). Using a rich suite of irregular parallel applications, and a mature Concert system, we evaluate the programming e ort for the following irregular parallel computations: graphics (polygon overlay and hierarchical radiosity), N-body codes (barnes-hut and fast multipole method), adaptive mesh codes (structured adaptive mesh re nement), and symbolic computation (gr obner basis and phylogeny). For each application, delivered performance is close to the best possible. Detailed descriptions of the parallelization and optimization steps provide insight into the concerns the programming system (model and implementation) succeeded in automating, and those that remained. In addition, such descriptions also provide insight into the key aspects of parallelizing each application. Our experience indicates that a high-level concurrent object-oriented programmingmodel and a sophisticated implementation can eliminatemany concerns, easing the programming of irregular parallel applications. 3 First, despite the fact that the underlying machines are distributed memories, programmers are freed from explicit namespace management, computation granularity (procedure and data), and low-level memory race management. Second, while in most cases, programmers still needed to express application speci c data locality and load balance, the orthogonal framework for functionality and data placement eased this e ort by allowing radical changes in data layout with modest code changes. While the decomposition of computation and data layout is similar conceptually to that in HPF [13], the decompositions used for our applications are irregular. Finally, while quantitative metrics are only moderately indicative of programming e ort, they nonetheless provide a tangible point of comparison. Over the seven applications only modest code changes (less than 5% of the lines) were required, mostly to express the careful data locality and load balance needed to achieve top performance. Of course, given the diversity of applications studied, several required more detailed control over data locality and load balance. In applications employing heuristic methods, task ordering control is required [21]. And, in several applications, explicit thread placement (complementary to data placement and owner computes) was a more convenient perspective. Finally, the radiosity, grobner, and phylogeny applications beneted from annotations for relaxed data consistency. The remainder of the paper is organized as follows: Section 2 details the key elements of the programming interface, its implementation, and the irregular application suite. Section 3 presents our methodology used in Section 4 to describe the algorithmic and data structure of each application and summarize the e orts required to achieve high parallel performance. Quantitative performance data and an illustration of the performance impact of each type of program transformation is shown in Section 5. We conclude with a discussion and summary in Sections 6 and 7. 2 Background In evaluating a programming approach, our goal is to identify the concerns which must be addressed by a programmer to achieve good performance and how those concerns are managed. Any such experimental evaluation must be done in the context of an actual programming system with its attendant strengths and 4 shortcomings. Finally, the experiments must involve a community of programmers and particular application programs. We describe in turn, the basic programming interface, interfaces for performance optimization, and the compiler and runtime technology of the Illinois Concert system. We conclude by discussing the application programs used in the study (e.g. the workload). 2.1 Basic Programming Interface Our programming interface is a basic object-oriented programming system augmented with simple extensions for concurrency. Thus, programmers can take sequential programs and move them into a parallel environment with little or no change. Then, concurrency can be added as appropriate. The basic model is based on C++, providing a single namespace, scalars and objects, and single inheritance. For further details on the programming model (Illinois Concert C++ or ICC++) see [41]. Simple extensions for concurrency include annotating standard blocks (i.e. compound statements) and loops with the conc keyword. A conc block de nes a partial order amongst its statements, allowing concurrency while preserving local data dependences. Thus, conc can often be applied to existing blocks. Also, conc indicates non-binding concurrency, allowing programmers to specify concurrency and depend on the underlying system to create threads as required. A simple semantics for object concurrency provides synchronization | method invocations on an object execute as if they had exclusive access. The state of the object is sequentially consistent; however operations across multiple objects may not be. This raises the level of consistency from single memory

Evaluating High Level Parallel Programming Support for Irregular Applications in ICC++