Optimization of parallel applications under new many-core architectures is challenging even for regular applications. Successful strategies inherited from previous generations of parallel or serial architectures just return incremental gains in performance and further optimization and tuning are required. We argue that conservative static optimizations are not the best fit for modern many-core architectures. The limited advantages of static techniques come from the new scenarios present in many-cores: Plenty of thread units sharing several resources under different coordination mechanisms.

Advanced many-core CPU chips already have a few hundreds of processing cores (e.g., 160 cores in an IBM Cyclops-64 chip) and more and more processing cores become available as computer architecture progresses. The underlying runtime systems of such architectures need to efficiently serve hundreds of processors at the same time, requiring all basic data structures within the runtime to maintain unprecedented throughput. In this paper, we analyze the throughput requirements that must be met by algorithms in runtime systems to be able to handle hundreds of simultaneous operations in real time. We reach a surprising conclusion: Many traditional algorithm techniques are poorly suited for highly parallel computing environments because of their low throughput. We reach the conclusion that the intrinsic throughput of a parallel program depends on both its algorithm and the processor architecture where the program runs. We provide theory to quantify the intrinsic throughput of algorithms, and we provide a few examples, where we describe the intrinsic throughput of existing, common algorithms. Then, we go on to explain how to follow a throughput-oriented approach to develop algorithms that have very high intrinsic throughput in many core architectures. We compare our throughput-oriented algorithms with other well known algorithms that provide the same functionality and we show that a throughput-oriented design produces algorithms with equal or faster performance in highly concurrent environments. We provide both theoretical and experimental evidence showing that our algorithms are excellent choices over other state of the art algorithms. The major contributions of this paper are (1) motivating examples that show the importance of throughput in concurrent algorithms; (2) a mathematical framework that uses queueing theory to describe the intrinsic throughput of algorithms; (3) two highly concurrent algorithms with very high intrinsic throughput that are useful for task management in runtime systems; and (4) extensive experimental and theoretical results that show that for highly parallel systems, our proposed algorithms allow greater or at least equal scalability and performance than other well-known similar state-of-the-art algorithms.

Summary form only given. The popularity of serial execution paradigms in the High Performance Computing (HPC) field greatly hinders the ability of computational scientists to develop and support massively parallel programs. Programmers are left with languages that are inadequate to express parallel constructs, being forced to take decisions that are not directly related to the programs they write. Computer architects are forced to support sequential memory semantics only because serial languages require them and operating system designers are forced to support slow synchronization operations. This poster addresses the development and execution of HPC programs in many-core architectures by introducing the Time Iterated Dependency Flow (TIDeFlow) execution model. In TIDeFlow, programmers specify the precedence relations between computations without dealing with implementation details related to synchronization or scheduling. TIDeFlow is a graph-based model inspired by dataflow: Computations in a program are expressed as actors whose dependencies are represented by arcs. TIDeFlow departs from other dataflow models (1) in that actors represent parallel loops as the basic building block of HPC programs, (2) in that arcs between actors represent dependencies of any kind (data, control or other) and (3) in that arc weights allow delaying tokens to provide support for pipelining. TIDeFlow is related to other dataflow models (an excellent survey can be found in [1]) in the idea of executing several computations into a single actor as in Macro Dataflow[2] and in allowing multiple, concurrent executions of the same actor through coloring of tokens as in Dynamic Dataflow[3]. The resulting TIDeFlow model expresses HPC programs as directed graphs with weighted nodes and weighted arcs that represent parallel loops and loop carried dependencies respectively. The model is useful to support task pipelining, task migration, and distributed control. An implementation of TIDeFlow was developed for Cyclops- 64[4], a 160-core architecture by IBM. The implementation resulted in new, highly concurrent algorithms-such as the HT-Queue[4]and in development of efficient representation of runtime system primitives such as polytasks[5]. The implementation is supported by a number of software tools including a graph programming model, a parallel intermediate representation form and a fully distributed runtime system. The effectiveness of TIDeFlow was tested using several HPC programs, including FDTD in 1 and 2 dimensions [6], Matrix Multiply, and FFT. In all cases, the programs were run using Cyclops-64, allowing excellent studies in scalability, performance, parallelism and overhead. The results of the experiments, presented in [4] and [5] show that TIDeFlow can efficiently support very fine grained execution due to its very low overhead and its distributed nature. The experiments also show excellent scalability, al- lowing close-to-linear scalability for 156 processors executing matrix multiply. The experiments also showed the advantages for development: Expressing dependencies using a graph was found to be easier than placing hand-coded synchronization constructs inside programs. The performance of the TIDeFlow runtime system was carefully measured, showing that it uses very few clock cycles to create, schedule and terminate tasks. The runtime system is fully distributed and lock-free, allowing runtime operations to be insensible to the load of the system. This poster introduces TIDeFlow by presenting (1) its graph programming model (weighted nodes and wighted arcs), (2) a description of composability in TIDeFlow, which allows the use of programs to build larger programs, (3) a brief description of the TIDeFlow runtime system and (4) a summary of the excellent results obtained, both in scalability and overhead for FDTD in 1 and 2 dimensions, Matrix Multiply, and FFT. This work contributes to the state of the art by: (1) Presenting a new execution model, (2) presenting an overview of the design of a decentralized, fully distributed runtime system, (3) conveying the idea that HPC applications can be efficiently expressed as weighted graphs and (4) showing that common techniques such as double buffering and task pipelining can be an intrinsic part of a programming model rather than a technique used by the programmer.

This paper reports a study of mapping the Finite Difference Time Domain (FDTD) application to the IBM Cyclops-64 (C64) many-core chip architecture [1]. C64 is chosen for this study as it represents the current trend in computer architecture to develop a class of many-core architectures with distinct features e.g. software manageable on-chip memory hierarchy (vs. a hardware-managed data cache), high on-chip bandwidth, fine grain multithreading and synchronization, among others. Major results of our study include: 1. A good mapping of FDTD can effectively exploit the on-chip parallelism of C64-like architectures and show good performance and scalability. 2. Such performance improvement is derived by employing a number of code optimization techniques such as time skewing and split tiling that judiciously exploit the architecture features described in (1). 3. High performance requires maximum reuse of on-chip memory, which is obtained by tiling with non conventional tile shapes. 4. Such code optimization techniques we used in (2) and tiling such as the one used in (3) should be implementable within a reasonable compilation framework, opening a new set of possibilities for compiler optimizations.

Automatic library generators, such as ATLAS, Spiral and FFTW, are promising technologies to generate efficient code for different computer architectures. The library generators usually tune programs using two layers of optimizations: the search at the algorithm level, and the optimization for micro kernels. The micro optimizations are important for the performance of library, because the optimized micro kernels are the bases of algorithm level search, and have a great impact on the overall performance of the generated libraries. A successfully optimized micro kernel requires thorough understanding of the interaction between architectural features and highly optimized code. However, literature on library generators focus more on the algorithm level optimization, and usually give only simple discussion of how kernel codes are generated and tuned. As a result, the optimization of micro kernels is still an art that depends on individual expertise, and is insufficiently documented. In this paper, we study the problem of how to generate efficient FFT kernels. We apply a series of micro optimizations, for example, memory hierarchy locality enhancements, to several FFT routines, and use hardware counters to observe the interactions between those optimizations with Intel Pentium 4 and the latest Intel core 2 architecture. We achieve good speedups, and more importantly, we present methods that can be used to generate high-performance FFT kernels on different architectures.