In mobile and edge devices, reducing energy consumption and achieving high energy efficiency is the most critical system design aspect. For matrix multiplication, one of the widely used workloads, achieving this goal requires high resource utilization since dynamic power only represent a fraction of the total power. Generally, there is a trade-off between minimizing execution time and minimizing energy consumption for the workload, e.g. [1]-[3] We present a study of the effect on 1) power consumption on the Myriad-2 Vision Processing Unit (VPU) due to matrix initialization for single-precision matrix multiplication, SGEMM, and 2) energy efficiency of clock gating of processing cores.

Reducing energy consumption and achieving high energy efficiency in computation has become the top priority in High Performance Computing. High energy efficiency generally requires high resource utilization since energy demand for any applications and architectures is dependent on active time. We show that by using DMA the 28nm CMOS node Myriad-2 Vision Processing Unit can achieve 25 GFLOPs/W for FP32 matrixmultiplication. Our main contributions are: (i) An analysis of data transfer needs for inner and outer-product formulations of matrix multiplication with respect to the Myriad-2 memory hierarchy, (ii) An efficient use of DMA for managing matrix block transfers between on-chip and main memory (iii) A detailed analysis of the effects of matrix block shapes and DRAM page faults on performance and energy efficiency.

Summary Important computational physics problems are often large‐scale in nature, and it is highly desirable to have robust and high performing computational frameworks that can quickly address these problems. However, it is no trivial task to determine whether a computational framework is performing efficiently or is scalable. The aim of this paper is to present various strategies for better understanding the performance of any parallel computational frameworks for solving PDEs. Important performance issues that negatively impact time‐to‐solution are discussed, and we propose a performance spectrum analysis that can enhance one's understanding of critical aforementioned performance issues. As proof of concept, we examine commonly used finite element simulation packages and software and apply the performance spectrum to quickly analyze the performance and scalability across various hardware platforms, software implementations, and numerical discretizations. It is shown that the proposed performance spectrum is a versatile performance model that is not only extendable to more complex PDEs such as hydrostatic ice sheet flow equations but also useful for understanding hardware performance in a massively parallel computing environment. Potential applications and future extensions of this work are also discussed.

Abstract The SweGrid Accounting System (SGAS) allocates capacity in collaborative Grid environments by coordinating enforcement of Grid‐wide usage limits as a means to offer usage guarantees and prevent overuse. SGAS employs a credit‐based allocation model where Grid capacity is granted to projects via Grid‐wide quota allowances that can be spent across the Grid resources. The resources collectively enforce these allowances in a soft, real‐time manner. SGAS is built on service‐oriented principles with a strong focus on interoperability and Web services standards. This article covers the SGAS design and implementation, which, besides addressing inherent Grid challenges (scale, security, heterogeneity, decentralization), emphasizes generality and flexibility to produce a customizable system with lightweight integration into different middleware and scheduling system combinations. We focus the discussion around the system design, a flexible allocation model, middleware integration experiences and scalability improvements via a distributed virtual banking system, and finally, an extensive set of testbed experiments. The experiments evaluate the performance of SGAS in terms of response times, request throughput, overall system scalability, and its performance impact on the Globus Toolkit 4 job submission software. We conclude that, for all practical purposes, the quota enforcement overhead incurred by SGAS on job submissions is not a limiting factor for the job‐handling capacity of the job submission software. Copyright © 2008 John Wiley & Sons, Ltd.

Increased complexity of memory systems to ameliorate the gap between the speed of processors and memory has made it increasingly harder for compilers to optimize an arbitrary code within a palatable amount of time. With the emergence of multicore (CMP), multiprocessor (SMP) and hybrid shared memory multiprocessor architectures, achieving high e ciency is becoming even more challenging. To address the challenge to achieve high e ciency in performance critical applications, domain speci c frameworks have been developed that aid the compilers in scheduling the computations. We have developed a portable framework for the Fast Fourier Transform (FFT) that achieves high e ciency by automatically adapting to various architectural features. Adapting to parallel architectures by searching through all the combinations of schedules (plans) is an expensive task, even when the search is conducted in parallel. In this paper, we develop heuristics to simplify the generation of better schedules for parallel FFT computations on CMP/SMP systems. We evaluate the performance of OpenMP and PThreads implementations of FFT on a number of latest architectures. The performance of parallel FFT schedules is compared with that of the best plan generated for sequential FFT and the speedup for di erent number of processors is reported. In the end, we also present a performance comparison between the UHFFT and FFTW implementations.

We present the SweGrid Accounting System (SGAS) — a decentralized and standards-based system for Grid resource allocation enforcement that has been developed with an emphasis on a uniform data model and easy integration into existing scheduling and workload management software. The system has been tested at the six high-performance computing centers comprising the SweGrid computational resource, and addresses the need for soft, real-time quota enforcement across the SweGrid clusters. The SGAS framework is based on state-of-the-art Web and Grid services technologies. The openness and ubiquity of Web services combined with the fine-grained resource control and cross-organizational security models of Grid services proved to be a perfect match for the SweGrid needs. Extensibility and customizability of policy implementations for the three different parties that the system serves (the user, the resource manager, and the allocation authority) are key design goals. Another goal is end-to-end security and single sign-on, to allow resources to reserve allocations and charge for resource usage on behalf of the user. We conclude this paper by illustrating the policy customization capabilities of SGAS in a simulated setting, where job streams are shaped using different modes of allocation policy enforcement. Finally, we discuss some of the early experiences from the production system.

In this work, we describe new strategies for scheduling and executing workflow applications on grid resources using the GrADS [Ken Kennedy et al., 2002] infrastructure. Workflow scheduling is based on heuristic scheduling strategies that use application component performance models. The workflow is executed using a novel strategy to bind and launch the application onto heterogeneous resources. We apply these strategies in the context of executing EMAN, a bio-imaging workflow application, on the grid. The results of our experiments show that our strategy of performance model based, in-advance heuristic workflow scheduling results in 1.5 to 2.2 times better makespan than other existing scheduling strategies. This strategy also achieves optimal load balance across the different grid sites for this application.

In this work, we describe new strategies for scheduling and executing workflow applications on Grid resources using the GrADS infrastructure. Workflow scheduling is based on heuristic scheduling strategies that use combined computational and memory hierarchy application component performance models. The workflow is executed using a novel strategy to bind and launch the application onto heterogeneous resources. We apply these strategies in the context of launching EMAN, a bio-imaging workflow application, onto the Grid.

In this paper, we present an Open Grid Services Architecture (OGSA)-based decentralized allocation enforcement system, developed with an emphasis on a consistent data model and easy integration into existing scheduling, and workload management software at six independent high-performance computing centers forming a Grid known as SweGrid. The Swedish National Allocations Committee (SNAC) allocates resource quotas at these centers to research projects requiring substantial computer time. Our system, the SweGrid Accounting System (SGAS), addresses the need for soft real-time allocation enforcement on SweGrid for cross-domain job submission. The SGAS framework is based on state-of-the-art Web and Grid services technologies. The openness and ubiquity of Web services combined with the fine-grained resource control and cross-organizational security models of Grid services proved to be a perfect match for the SweGrid needs. Extensibility and customizability of policy implementations for the three different parties the system serves (the user, the resource manager, and the allocation authority) are key design goals. Another goal is end-to-end security and single sign-on, to allow resources-selected based on client policies-to act on behalf of the user when negotiating contracts with the bank in an environment where the six centers would continue to use their existing accounting policies and tools. We conclude this paper by showing the feasibility of SGAS, which is currently being deployed at the production sites, using simulations of reservation streams. The reservation streams are shaped using soft computing and policy-based algorithms.

In this paper we present an adaptive and portable software library for the fast Fourier transform (FFT). The library consists of a number of composable blocks of code called codelets, each computing a part of the transform. The actual FFT algorithm used by the code is determined at run-time by selecting the fastest strategy among all possible strategies, given available codelets, for a given transform size. We also presentanefficient automatic method of generating the library modules by using a special--purpose compiler. The code generator is written in C and it generates a library of C codelets. The code generator is shown to be flexible and extensible and the entire library can be generated in a matter of seconds. Wehaveevaluated the library for performance on the IBM--SP2, SGI--2000, HP--Exemplar and Intel Pentium systems. We use the results from these evaluations to build performance models for the FFT library on different platforms. The library is shown to be portable, adaptive and efficient. 1.

The high performance Fortran (HPF) benchmark suite HPFBench is designed for evaluating the HPF language and compilers on scalable architectures. The functionality of the benchmarks covers scientific software library functions and application kernels that reflect the computational structure and communication patterns in fluid dynamic simulations, fundamental physics, and molecular studies in chemistry and biology. The benchmarks are characterized in terms of FLOP count, memory usage, communication pattern, local memory accesses, array allocation mechanism, as well as operation and communication counts per iteration. The benchmarks output performance evaluation metrics in the form of elapsed times, FLOP rates, and communication time breakdowns. We also provide a benchmark guide to aid the choice of subsets of the benchmarks for evaluating particular aspects of an HPF compiler. Furthermore, we report an evaluation of an industry-leading HPF compiler from the Portland Group Inc. using the HPFBench benchmarks on the distributed-memory IBM SP2

We present a general data parallel formulation for highly irregular problems in High Performance Fortran (HPF). Our formulation consists of(1) a method for linearizing irregular data structures (2) a data parallel implementation (in HPF) of graph partitioning algorithms applied to the linearized data structure, (3) techniques for expressing irregular communication and nonuniform computations associated with the elements of linearized data structures.We demonstrate and evaluate our formulation on a parallel, hierarchical N--body method for the evaluation of potentials and forces of nonuniform particle distributions. Our experimental results demonstrate that efficient data parallel (HPF) implementations of highly nonuniform problems are feasible with the proper language/compiler/runtime support. Our data parallel N--body code provides a much needed "benchmark" code for evaluating and improving HPF compilers.

The O(N) hierarchical N-body algorithms and Massively Parallel Processors allow particle systems of 100 million particles or more to be simulated in acceptable time. We present a data-parallel implementation of Anderson's method and demonstrate both efficiency and scalability of the implementation on the Connection Machine CM-5/5E systems. The communication time for large particle systems amounts to about 10-25%, and the overall efficiency is about 35%. The evaluation of the potential field of a system of 100 million particles takes 3 minutes and 15 minutes on a 256 node CM-5E, giving expected four and seven digits of accuracy, respectively. The speed of the code scales linearly with the number of processors and number of particles.

ROMM is a class of Randomized, Oblivious, Multi-phase, Minimal routing algorithms.ROMM routing offers a potential for improved performance compared to both fully randomized algorithms and deterministic oblivious algorithms, under both light and heavy loads.ROMM routing also offers close to best case performance for many common routing problems.In previous work, these claims were supported by extensive simulations on binary cube networks [30, 31], Here we present analytical and empirical results for ROMM routing on wormhole routed mesh and torus networks.Our simulations show that ROMM algorithms can perform several represent ative routing tasks 1,5 to 3 times faster than fully randomized algorithms, for medium-sized networks.Furthermore, ROMM algorithms are always competitive with deterministic, oblivious routing, and in some cases, up to 2 times faster. 1

We present a new algorithm for conversion between binary code and binary-reflected Gray code that requires approximately 2 K/3 element transfers in sequence for K elements per node, compared to K element transfers for previously known algorithms. For a binary cube of n=2 dimensions the new algorithm degenerates to yield a complexity of 2 K/+1 element a transfers, which is optimal. The new algorithm is optimal to within a multiplicative factor of 4/3 with respect to the best known 3 lower bound for any routing strategy. We show that the minimum number of element transfers for minimum path length routing is K with concurrent communication on all channels of every node of a binary cube.>

We present a linear algebraic formulation for a class of index transformations such as Gray code encoding and decoding, matrix transpose, bit reversal, vector reversal, shuffles, and other index or dimension permutations. This formulation unifies, simplifies, and can be used to derive algorithms for hypercube multiprocessors. We show how all the widely known properties of Gray codes, and some not so well-known properties as well, can be derived using this framework. Using this framework, we relate hypercube communications algorithms to Gauss-Jordan elimination on a matrix of 0's and 1's.>

No abstract available.

We have implemented Quantum Chromo-Dynamics (QCD) on the massively parallel Connection Machine in *Lisp. The code uses dynamical Wilson fermions and the Hybrid Monte Carlo Algorithm (HMCA) to update the lattice. We describe our program and give performance measurements for it. With no tuning or optimization, the code runs at approximately 500 to 1000 MFLOPS on a 64-K Connection Machine, model CM-2, depending on the VP ratio.

A P(k, d) hyper-pyramid is a level structure of k Boolean cubes where the cube at level i is of dimension id, and a node at level i - 1 connects to every node in a d dimensional Boolean subcube at level i, except for the leaf level k. Hyper-pyramids contain pyramids as proper subgraphs. We show that a P(k, d) hyper-pyramid can be embedded in a Boolean cube with minimal expansion and dilation d. The congestion is bounded from above by 2d+1/d+2 and from below by 1 + ⌈2d-d/kd+1⌉. For P(k, 2) hyper-pyramids we present a dilation 2 and congestion 2 embedding. As a corollary a complete n-ary tree can be embedded in a Boolean cube with dilation max(2, ⌈log2 n⌉) and expansion 2k⌈log2 n⌉ + 1/nk+1-1/n-1. We also discuss multiple pyramid embeddings.

A data parallel implementation of the multiplication of matrices of arbitrary shapes and sizes is presented. A systolic algorithm based on a rectangular processor layout is used by the implementation. All processors contain submatrices of the same size for a given operand. Matrix-vector multiplication is used as a primitive for local matrix-matrix multiplication in the Connection Machine system CM-2 implementation. The peak performance of the local matrix-matrix multiplication is in excess of 20 Gflops s-1. The overall algorithm including all required data motion has a peak performance of 5.8 Gflops s-1.

We describe a radix-2 FFT implementation on the Connection Machine. The FFT implementation pipelines successive FFT stages to make full use of the communication capability of the network interconnecting processors, when there are multiple elements assigned to each processor. Of particular interest in distributed memory architectures such as the Connection Machine is the allocation of twiddle factors to processors. We show that with a consecutive data allocation scheme and normal order input a decimation-in-time FFT results in a factor of log2N less storage for twiddle factors than a decimation-in-frequency FFT for N processors. Similarly, with consecutive storage and bit-reversed input a decimation-in-frequency FFT requires a factor of log2N less storage than a decimation-in-time FFT. The performance of the local FFT has a peak of about 3 Gflops/s. The “global” FFT has a peak performance of about 1.7 Gflops/s.

A data parallel formulation of the finite element method is described. The data structures and the algorithms for stiffness matrix generation and the solution of the equilibrium equations are presented briefly. The generation of the elemental stiffness matrices requires no communication, even though each finite element is distributed over several processors. The conjugate gradient method with a diagonal preconditioner has been used for the solution of the resulting sparse linear system. This formulation has been implemented on the Connection Machine® model CM-2. The simulations reported in this article investigate the influence of the mesh discretization and the interpolation order on the convergence behavior of the conjugate gradient method. A linear dependence of the convergence behavior on the mesh discretization parameter is observed. In addition, the convergence rate depends on the interpolation order p as Ο(p1.6). The peak floating point rate (single-precision) for the evaluation of the stiffness matrix is approximately 2.4 Gflops s-1. The iterative solver peaks at nearly 850 Mflops s-1.

Explicit methods for the solution of fluid flow problems are of considerable interest in supercomputing. These methods parallelize well. The treatment of the boundaries is of particular interest both with respect to the numeric behavior of the solution, and the computational efficiency. We have solved the three-dimensional Euler equations for a twisted channel using second-order, centered difference operators, and a three stage Runge-Kutta method for the integration. Three different fourth-order dissipation operators were studied for numeric stabilization: one positive definite, [8], one positive semidefinite, [3], and one indefinite. The operators only differ in the treatment of the boundary. For computational efficiency all dissipation operators were designed with a constant bandwidth in matrix representation, with the bandwidth determined by the operator in the interior. The positive definite dissipation operator results in a significant growth in entropy close to the channel walls. The other operators maintain constant entropy.

Abstract One data‐independent and one data‐dependent algorithm for the computation of image histograms on parallel computers are presented, analysed and implemented on the Connection Machine system CM‐2. The data‐dependent algorithm has a lower requirement on communication bandwidth by only transferring bins with a non‐zero count. Both algorithms perform all‐to‐all reduction, which is implemented through a sequence of exchanges as defined by a butterfly network. The two algorithms are compared based on predicted and actual performance on the Connection Machine CM‐2. With few pixels per processor the data‐dependent algorithm requires in the order of √B data transfers for B bins compared to B data transfers for the data‐independent algorithm. As the number of pixels per processor grows the advantage of the data‐dependent algorithm decreases. The advantage of the data‐dependent algorithm increases with the number of bins of the histogram.

Four different communication problems are addressed in Boolean n-cube configured multiprocessors: (1) one-to-all broadcasting: distribution of common data from a single source to all other nodes; (2) one-to-all personalized communication: a single node sending unique data to all other nodes; (3) all-to-all broadcasting: distribution of common data from each node to all other nodes; and (4) all-to-all personalized communication: each node sending a unique piece of information to every other node. Three communication graphs (spanning trees) for the Boolean n-cube are proposed for the routing, and scheduling disciplines provably optimum within a small constant factor are proposed. With appropriate scheduling and concurrent communication on all ports of every processor, routings based on these two communication graphs offer a speedup of up to n/2, and O( square root n) over the routings based on the spanning binomial tree for cases (2)-(4) respectively. All three spanning trees offer optimal communication times for cases (2)-(4) and concurrent communication on all ports of every processor. Timing models and complexity analysis are verified by experiments on a Boolean-cube-configured multiprocessor.>

This paper presents a few algorithms for embedding loops and multidimensional arrays in hypercubes with emphasis on proximity preserving embeddings. A proximity preserving embedding minimizes the need for communication bandwidth in computations requiring nearest neighbor communication. Two storage schemes for “large” problems on “small” machines are suggested and analyzed, and algorithms for matrix transpose, multiplying matrices, factoring matrices, and solving triangular linear systems are presented. A few complete binary tree embeddings are described and analyzed. The data movement in the matrix algorithms is analyzed and it is shown that in the majority of cases the directed routing paths intersect only at nodes of the hypercube allowing for a maximum degree of pipelining.

A graph model is proposed to capture the topological properties of metal-oxide semiconductor (MOS) transistors and interconnections among transistors. A set of algorithms is devised for the enumeration of layout topologies of a circuit from its graph model. Layout topologies are presented in stick diagrams. The algorithms select a set of embedded layout topologies with the “fewest” number of jumpers for layout generation and compaction. Layouts for circuits with up to 36 transistors have been generated successfully. The layouts corresponding to the topologies generated and selected by the algorithms are, in most cases, smaller than compact hand layouts. The worst case computational complexity is O(n 2), where n is the number of transistors in the circuit.

We present concurrent algorithms for the solution of narrow banded systems on ensemble architectures, and analyze the communication and arithmetic complexities of the algorithms. The algorithms consist of three phases. In phase 1, a block tridiagonal system of reduced size is produced through largely local operations. Diagonal dominance is preserved. If the original system is positive, definite, and symmetric, so is the reduced system. It is solved in a second phase, and the remaining variables obtained through local back substitution in a third phase. With a sufficient number of processing elements, there is no first and third phase. We investigate the arithmetic and communicationcomplexity of Gaussian elimination and block cyclic reduction for the solution of the reduced system on boolean cubes, perfect shuffle and shuffle-exchange networks, binary trees, and linear arrays. With an optimum number of processors, the minimum solution time on a linear array is of an order that ranges from O(m 2 √Nm) to O(m 3 + m 3 log 2 ( N/m )) depending on the bandwidth, the dimension of the problem, and the times for communication and arithmetic. For boolean cubes, cube-connected cycles, prefect shuffle and shuffle-exchange networks, and binary trees, the minimum time is O(m 3 +m 3 log 2 (N/m)) including the communication complexity