The slowdown in technology scaling puts architectural features at the forefront of the innovation in modern processors. This article presents a Metric-Guided Method (MGM) that extends Top-Down analysis with carefully selected, dynamically adapted metrics in a structured approach. Using MGM, we conduct two evaluations at the microarchitecture and the Instruction Set Architecture (ISA) levels. Our results show that simple optimizations, such as improved representation of CISC instructions, broadly improve performance, while changes in the Floating-Point execution units had mixed impact. Overall, we report 10 architectural insights—at the microarchitecture, ISA, and compiler fronts—while quantifying their impact on the SPEC CPU benchmarks.

A detailed analysis of power consumption at low system levels becomes important as a means for reducing the overall power consumption of a system and its thermal hot spots. This work presents a new power estimation method that allows understanding the power breakdown of an application when running on modern processor architecture such as the newly released Intel Skylake processor. This work also provides a detailed power and performance characterization report for the SPEC CPU2006 benchmarks, analysis of the data using side-by-side power and performance breakdowns, as well as few interesting case studies.

Tools that provide optimization hints for program developers are facing severe obstacles and often unable to provide meaningful guidance on how to parallelize real-life applications. The main reason is due to the high code complexity and its large size when considering commercially valuable code. Such code is often rich with pointers, heavily nested conditional statements, nested while-based loops, function calls, etc. These constructs prevent existing compiler analysis from extracting the full parallelization potential. We propose a new paradigm to overcome this issue by automatically transforming the code' into a much simpler skeleton-like form that is more conductive for auto-parallelization. We then apply existing tools of source-level automatic parallelization on the skeletonized code in order to expose possible parallelization patterns. The skeleton code, along with the parallelized version, are then provided to the programmer in the form of an Integrated Development Environment (IDE) recommendation. The proposed skeletonization algorithm replaces pointers by integer indexes and C-struct references by references to multi-dimensional arrays. For example, the loop while(p ≠ NULL) {p → val + +; p = p → next;} will be skeletonized to: for(Ip = 0; Ip <; N; Ip + +){Aval[Ip] + +;} where Aval[] holds the embedding of the original list. Consequently, the main goal of the skeletonization process is to embed pointer-based data structures into arrays. Though the skeletonized code is not semantically equivalent to the original code, it suggests a possible parallelization pattern for the selected code segment and can be used as an effective parallelization hint to the programmer. We applied the method on the SPEC CPU benchmarks and the skeletonization process detected 27 percent additional loops that can be parallelized/vectorized on top of the compiler auto-parallelizer/vectorizer. A performance gain of up to 45 percent was measured for benchmarks that were manually parallelized based on the generated skeleton code.

We propose automatic synthesis of application specific instruction set processors (ASIPs). We use pipeline execution of multi-op machine-instructions, e.g., *(reg1*reg2) = (*reg3) + (*reg4) (C-syntax) an instruction with three memory stages and two arithmetic stages pipeline. The problem is, for a given set of loops, to find a pipeline configuration and a multi-op ISA that maximizes the IPC (instructions per cycle) while minimizing the resource usage and the cost of interconnections to the register-file of the resulting CPU. The algorithm is based on finding an efficient cover of a large graph by a small set of convex sub-graphs gis that are consistent with a given structure of a pipeline. Unlike previous works, gis are not synthesized to circuits that are executed in a co-processor mode but rather both gis and the rest of the program are executed by the same set of multiop pipeline units. In this way we eliminate the overhead associated with the co-processor mode of regular ASIPs but maintain high values of IPC of these ASIPs. The main advantage of using pipeline execution of multi-op versus VLIW instructions is shown to be the cost of interconnections between the CPU's execution units and the register file. Thus, we devise a grading function that for each possible multi-op pipeline configuration balance between the expected IPC (Instructions Per Cycle) and the complexity of the interconnections. Using this grading function we show that in most cases the VLIW configuration is not always the best choice.

Manycore shared memory architectures hold a significant premise to speed up and simplify SOCs. Using many homogeneous small-cores will allow replacing the hardware accelerators of SOCs by parallel algorithms communicating through shared memory. Currently shared memory is realized by maintaining cache-consistency across the cores, caching all the connected cores to one main memory module. This approach, though used today, is not likely to be scalable enough to support the high number of cores needed for highly parallel SOCs. Therefore we consider a theoretical scheme for shared memory wherein: the shared address space is divided between a set of memory modules; and a communication network allows each core to access every such module in parallel. Load-balancing between the memory modules is obtained by rehashing the memory address-space. We have designed a simple generic shared memory architecture, synthesized it to 2,4,8,,..1024-cores for FPGA virtex-7 and evaluated it on several parallel programs. The synthesis results and the execution measurements show that, for the FPGA, all problematic aspects of this construction can be resolved. For example, unlike ASICs, the growing complexity of the communication network is absorbed by the FPGA's routing grid and by its routing mechanism. This makes this type of architectures particularly suitable for FPGAs. We used 32-bits modified PACOBLAZE cores and tested different parameters of this architecture verifying its ability to achieve high speedups. The results suggest that re-hashing is not essential and one hash-function suffice (compared to the family of universal hash functions that is needed by the theoretical construction).

Tools that provide optimization hints for program developers are facing severe obstacles and often unable to provide meaningful guidance on how to parallelize real--life applications. The main reason is due to the high code complexity and its large size when considering commercially valuable code. Such code is often rich with pointers, heavily nested conditional statements, nested while--based loops, function calls, etc. These constructs prevent existing compiler analysis from extracting the full parallelization potential. We propose a new paradigm to overcome this issue by automatically transforming the code into a much simpler skeleton-like form that is more conductive for auto-parallelization. We then apply existing tools of source--level automatic parallelization on the skeletonized code in order to expose possible parallelization patterns. The skeleton code, along with the parallelized version, are then provided to the programmer in the form of an IDE (Integrated Development Environment) recommendation.

Modern superscalar CPUs contain large complex structures and diverse execution units, consuming wide dynamic power range. Building a power delivery network for the worst-case power consumption is not energy efficient and often is impossible to fit in small systems. Instantaneous power excursions can cause voltage droops. Power management algorithms are too slow to respond to instantaneous events. In this article, we propose a novel compiler-directed framework to address this problem. The framework is validated on a 4th Generation Intel® Core™ processor and with simulator on output trace. Up to 16% performance speedup is measured over baseline for the SPEC CPU2006 benchmarks.

SIMD vector units implement only a subset of the operations used by vectorizing compilers, and there are multiple conflicting techniques to legalize arbitrary vector types into register-sized data types. Traditionally, type legalization is performed using a set of predefined rules, regardless of the operations used in the program. This method is not suitable to sparse SIMD instruction sets and often prevents the vectorization of programs. In this work we introduce a new technique for type legalization, namely vector element promotion, as well as a hybrid method for combining multiple techniques of type legalization. Our hybrid type legalization method makes decisions based on the knowledge of the available instruction set as well as the operations used in the program. Our experimental results demonstrate that program-dependent hybrid type legalization improves the execution time of vector programs, outperforms the existing legalization method, and allows the vectorization of workloads which were not vectorized before.

One of the main advantages of high-level synthesis (HLS) is the ability to synthesize circuits that can access multiple memory banks in parallel. Current HLS systems synthesize parallel memory references based on explicit array declarations in the source code. We consider the need to synthesize not only array references but also memory operations targeting pointers and dynamic data structures. This paper describes Automatic Memory Partitioning, a method for automatically synthesizing general data structures (arrays and pointers) into multiple memory banks for increased parallelism and performance. We use source code instrumentation to collect memory traces in order to detect linear memory access patterns. The memory traces are used to split data structures into disjoint memory regions and determine which segments may benefit from parallel memory access. We present an algorithm for allocating memory segments into multiple memory banks. Experiments show significant improvements in performance while conserving the number of memory banks.

Current high-level synthesis systems synthesize arithmetic units of a fixed known number of stages, and the scheduler mainly determines when units are activated. We focus on scheduling techniques for the high-level synthesis of pipelined arithmetic units where the number of stages of these operations is a free parameter of the synthesis. This problem is motivated by the ability to automatically create pipelined functional units, such as multipliers, with different pipe lengths. These units have different characteristics in terms of parallelism level, clock latency, frequency, etc. This article presents the Variable-length Pipeline Scheduler (VPS). The ability to synthesize variable-length pipelined units expands the known scheduling problem of high-level synthesis to include a search for a minimal number of hardware units (operations) and their desired number of stages. The proposed search procedure is based on algorithms that find a local minima in a d -dimensional grid, thus avoiding the need to evaluate all possible points in the space. We have implemented a C language compiler for VPS targeting FPGAs. Our results demonstrate that using variable-length pipeline units can reduce the overall resource usage and improve the execution time when synthesized onto an FPGA. The proposed search is sufficiently fast, taking only a few seconds, allowing an interactive mode of work. A comparison with xPilot shows a significant saving of hardware resources while maintaining comparable execution times of the resulting circuits. This work is an extension of a previous paper [Ben-Asher and Rotem 2008]

We consider the problem of synthesizing circuits (from C to Verilog) that are optimized to handle unpredictable latencies of memory operations. Unpredictable memory latencies can occur due to the use of on chip caches, DRAM memory modules, buffers/queues, or multiport memories. Typically, high-level synthesis compilers assume fixed and known memory latencies, and thus are able to schedule the code’s operations efficiently. The operations in the source code are scheduled into states of a state machine whose states will be synthesized to Verilog. The goal is to minimize scheduling length by maximizing the number of operations (and in particular memory operations) that are executed in parallel at the same state. However, with unpredictable latencies, there can be an exponential number of possible orders in which these parallel memory operations can terminate. Thus, in order to minimize the scheduling, we need a different schedule for any such order. This is not practical, and we show a technique of synthesizing a compact state machine that schedules only a small subset of these possible termination orders. Our results show that this compact state machine can improve the execution time compared to a regular scheduling that waits for the termination of all the active memory references in every state.

In this work we consider the problem of fast parallel evaluation of boolean circuits - namely to evaluate a boolean circuit C, with input leaf values, faster than its depth, which would practically require log depth iterations to complete. Finding a general parallel algorithm that can evaluate any circuit using log depth iterations is known as the Circuit Value Problem (CVP). The CVP and its approximations are known to be P-complete and therefore, a heuristically solution that practically works for all “real-computations” is sought. In this work we propose a new algorithm based on a two players game that can reduce the evaluation time of a boolean circuit C by upto min(h, min(log d, log co - d)) iterations where h is the maximal number of and-or alternations along any path in C and d (and co - d) is the algebraic degree (and co-degree) of C. This improves the theoretical bound of the MRK algorithm (Miller, Ramachandran and Kaltofen 86) for the case of parallel evaluation of boolean circuits. More importantly we show, via experiments, that for circuits emanating from real programs, the proposed algorithm can practically evaluate circuits in log - depth iterations. Each iteration can be evaluated in parallel using a connectivity step, and although it can be implemented using log-depth boolean circuits, we consider an optical switching realization that is based on Optical Ring Resonators (ORR). Due to quantum effects, propagating a light beam through a sequence of ORRs can be done with zero latency, thus making ORRs ideal for implementing the connectivity step required by the proposed algorithm. In order to obtain the needed experiments, we have extended the LLVM compiler to transform C-code into boolean circuits and then simulated the optical evaluation of these circuits using the proposed two player game. Our experiments indeed show that circuits emanating from real applications can be evaluated in log-depth iterations of the proposed algorithm and that the optical implementation is feasible.

Ad hoc networks are characterized by fast dynamic changes in the topology of the network. A known technique to improve quality of service (QoS) is to use multipath routing, where packets (voice/video/…) from a source to a destination travel in two or more maximal disjoint paths. We observe that the need to find a set of maximal disjoint paths can be relaxed by finding a set of paths S wherein only bottlenecked links are bypassed. In the proposed model, we assume that there is only one edge along a path in S that is a bottleneck and show that by selecting random paths in S the probability that bottlenecked edges get bypassed is high. We implemented this idea in the MRA system, which is a highly accurate visual ad hoc simulator currently supporting two routing protocols, AODV and MRA. We have extended the MRA protocol to use multipath routing by maintaining a set of random routing trees from which random paths can be easily selected. Random paths are allocated/released by threshold rules monitoring the session quality. The experiments show the following: (i) session QoS is significantly improved; (ii) the fact that many sessions use multiple paths in parallel does not depredate overall performances and (iii) the overhead in maintaining multipath in the MRA algorithm is negligible.1

A set of clusters (Grid) of multicore machines form an attractive platform for executing parallel programs. However, it is not clear how to program a single coherent parallel program over such a Grid of multicore machines (MCs). The main problem derives from the fact that the shared memory of each single MC machine cannot be scaled to run over a cluster of machines or a Grid. This is due to the fact that shared memory in a multicore machine is handled in hardware using a special cache coherency protocol, whereas over a cluster, the shared memory must be implemented in software using message passing. It is therefore, imperative for a Grid to devise a unified and coherent programming language that would combine both shared memory and message passing constructs, e.g., a language that combines the abilities of both OpenMP and MPI into one coherent language. The proposed language must produce parallel programs that are portable and can support the ability to scale the cluster without the need for re-compilation.

In High-Level Synthesis (HLS), extracting parallelism in order to create small and fast circuits is the main advantage of HLS over software execution. Modulo Scheduling (MS) is a technique in which a loop is parallelized by overlapping different parts of successive iterations. This ability to extract parallelism makes MS an attractive synthesis technique for loop acceleration. In this work we consider two problems involved in the use of MS which are central when targeting FPGAs. Current MS scheduling techniques sacrifice execution times in order to meet resource and delay constraints. Let “ideal” execution times be the ones that could have been obtained by MS had we ignored resource and delay constraints. Here we pose the opposite problem, which is more suitable for HLS, namely, how to reduce resource constraints without sacrificing the ideal execution time. We focus on reducing the number of memory ports used by the MS synthesis, which we believe is a crucial resource for HLS. In addition to reducing the number of memory ports we consider the need to develop MS techniques that are fast enough to allow interactive synthesis times and repeated applications of the MS to explore different possibilities of synthesizing the circuits. Current solutions for MS synthesis that can handle memory constraints are too slow to support interactive synthesis. We formalize the problem of reducing the number of parallel memory references in every row of the kernel by a novel combinatorial setting. The proposed technique is based on inserting dummy operations in the kernel and by doing so, performing modulo-shift operations such that the maximal number of parallel memory references in a row is reduced. Experimental results suggest improved execution times for the synthesized circuit. The synthesis takes only a few seconds even for large-size loops.

High level synthesis (HLS) is the field of transforming a high level programming language, such as C, into a register transfer level(RTL) description of the design. In HLS, binary synthesis is a method for synthesizing existing compiled applications for which the source code is not available. One of the advantages of FPGAs over software is the availability of multiple memory banks. Until now, binary synthesis systems have not made use of the multiple memory banks on FPGAs. In our work, we decompile the binary executable into an intermediate representation, and we target architectures with multiple memory banks and multiple memory ports. We present methods for detecting memory regions and synthesis of the decompiled code. The proposed methods accelerate the execution time of applications which use multiple memory regions concurrently.

In this study, we consider bytecode optimizations for Python, a programming language which combines object-oriented concepts with features of scripting languages, such as dynamic dictionaries. Due to its design nature, Python is relatively slow compared to other languages. It operates through compiling the code into powerful bytecode instructions that are executed by an interpreter. Python's speed is limited due to its interpreter design, and thus there is a significant need to optimize the language. In this paper, we discuss one possible approach and limitations in optimizing Python based on bytecode transformations. In the first stage of the proposed optimizer, the bytecode is expanded using function inline and loop unrolling. The second stage of transformations simplifies the bytecode by applying a complete set of data-flow optimizations, including constant propagation, algebraic simplifications, dead code elimination, copy propagation, common sub expressions elimination, loop invariant code motion and strength reduction. While these optimizations are known and their implementation mechanism (data flow analysis) is well developed, they have not been successfully implemented in Python due to its dynamic features which prevent their use. In this work we attempt to understand the dynamic features of Python and how these features affect and limit the implementation of these optimizations. In particular, we consider the significant effects of first unrolling and then inlining on the ability to apply the remaining optimizations. The results of our experiments indicate that these optimizations can indeed be implemented and dramatically improve execution times.

We propose an extension of Booth algorithm to perform multiplication of three numbers for faster FPGA implementation. This is based on the observation that when multiplying three numbers simultaneously the potential for arithmetic simplifications of intermediate terms increases. We use three types of simplifications of intermediate terms which are: representing consecutive sequences of 1 as a subtraction two powers of 2; eliminating opposite-sign powers of 2 from intermediate terms and combining multiple occurrences of the same power to a single power of 2. Our experiments show a significant improvement in the expected number of elementary operations and in the synthesis times for Xilinxpsilas Virtex-5.

A noise maker is a tool that seeds a concurrent program with conditional synchronization primitives, such as yield(), for the purpose of increasing the likelihood that a bug manifest itself. We introduce a novel fault model that classifies locations as "good", "neutral", or "bad," based on the effect of a thread switch at the location. Using the model, we explore the terms under which an efficient search for real-life concurrent bugs can be conducted. We accordingly justify the use of probabilistic algorithms for this search and gain a deeper insight of the work done so far on noise- making. We validate our approach by experimenting with a set of programs taken from publicly available multi-threaded benchmarks. Our empirical evidence demonstrates that real-life behavior is similar to one derived from the model.

Summary form only given. We consider the problem of compiling programs, written in a general high-level programming language, into hardware circuits executed by an FPGA (field programmable gate array) unit. In particular, we consider the problem of synthesizing nested loops that frequently access array elements stored in an external memory (outside the FPGA). We propose an aggressive compilation scheme, based on loop unrolling and code flattening techniques, where array references from/to the external memory are overlapped with uninterrupted hardware evaluation of the synthesized loop's circuit. We implement a restricted programming language called DOL based on the proposed compilation scheme and our experimental results provide preliminary evidence that aggressive compilation can be used to compile large code segments into circuits, including overlapping of hardware operations and memory references.

We define a new type of recurrence equations called "Simple Indexed Recurrences" (SIR). In this type of equations, ordinary recurrences are generalized to X[g(i)]=op/sub i/(X[f(i)], X[g(i)]), where f, g : {1...n}/spl rarr/{1...m}, op/sub i/(x, y) is a binary associative operator and g is distinct, i.e., /spl forall/i/spl ne/j g(i)/spl ne/g(j). This enables us to model certain sequential loops as a sequence of SIR equations. A parallel algorithm that solves a set of SIR equations will, in fact, parallelize sequential loops of the above type. Such a parallel SIR algorithm must be efficient enough to compete with the O(n) work complexity of the original loop. We show why efficient parallel algorithms for the related problems of list ranking and tree contraction, which require O(n) work, cannot be applied to solving SIR. We instead use repeated iterations of pointer jumping to compute the final values of X[] in n/p/spl middot/log p steps and n/spl middot/log p work, with p processors. A sequence of experiments was performed to test the effect of synchronous and asynchronous executions on the actual performance of the algorithm. These experiments show that pointer jumping requires O(n)) work in most practical cases of SIR loops. An efficient solution is given for the special case where we know how to compute the inverse of op/sub i/, and finally, useful applications of SIR to the well-known Livermore loops benchmark are presented.

Article Free Access Share on Communication-processor tradeoffs in limited resources PRAM Authors: Adnan Agbaria Technion, Haifa Technion, HaifaView Profile , Yosi Ben-Asher Haifa University Haifa UniversityView Profile , Ilan Newman Haifa University Haifa UniversityView Profile Authors Info & Claims SPAA '99: Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architecturesJune 1999 Pages 74–82https://doi.org/10.1145/305619.305628Published:01 June 1999Publication History 2citation240DownloadsMetricsTotal Citations2Total Downloads240Last 12 Months4Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We consider the problem of obtaining efficient (O(n) work) solutions for parallel evaluation of algebraic circuits.While obtaining efficient sequential evaluation of algebraic circuits is straightforward, this is not the case for parallel evaluation.The general result of Miller, Ramachandran and Kaltofen (1988) uses n3 processors for evaluating general circuits with arbitrary f, * operations.The parallelism in this result ia obtained through matrix multiplications, which is also the reason why so many processors are required.We thus chose to study a variant of algebraic circuits called LAC (Linear Algebraic Circuits), for which there is a different matrix form that eventually yields an efficient parallel algorithm.A lower bound of w(n .p) work (where p is the number of processors) for any algorithm which uses only sparse matrix multiplication steps to evaluate LACs in less than : sparse matrix multiplications steps is given.It follows that using matrix multiplications alone is not sufficient for obtaining a "fully" efficient (O(n) work) parallel solution, even for evaluating LACs.We present instead a CREW PRAM algorithm which, during execution, propagates computed values into future matrix products, and uses a special scheduling of the matrix multiplications to reduce constant factors of the execution time.This algorithm takes at most +-log'p steps; constant factors are important here due 18~3 to the need to compete with the sequential execution of the LAC.A "product measure" for LACs has been defined and a version of the algorithm that can improve the execution time according to this measure has been developed.Experiments for testing the effect of using this algorithm for "bad" cases of this measure has been performed.Finally, we show how such an algorithm can be used for manual parallelizing of sequential loops, which in many practical cases (of generalized recurrences) are actually LACs.Permission to make digital or hard copies of'all or part ot'this work for personal or classroom use is granted without fee provided that topics are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the tirst page.To copy otherwise, to republish, to post on semers or to redistribute to lists.rquires prior specific permission and/or a fee.

It is well known that the optimal solution for searching in a finite total order set is binary search. In binary search we divide the set into two "halves" by querying the middle element and continue the search on the suitable half. What is the equivalent of binary search when the set P is partially ordered? A query in this case is to a point $x\in P$, with two possible answers: "yes" indicates that the required element is "below" x or "no" if the element is not below x. We show that the problem of computing an optimal strategy for search in posets that are tree-like (or forests) is polynomial in the size of the tree and requires at most O(n 4 log 3 n ) steps. Optimal solutions of such search problems are often needed in program testing and debugging, where a given program is represented as a tree and a bug should be found using a minimal set of queries. This type of search is also applicable in searching classified large tree-like databases (e.g., the Internet).

The reconfigurable mesh (RN-MESH) can solve a large class of problems in constant time, including problems that require logarithmic time by other, even shared memory, models such as the PRAM with a similar number of processors. In this work we show that for the RN-MESH these constants can always be reduced to one, still using a polynomial number of processors. Given a reconfigurable mesh that computes a set of values in constant time, we show that it can be simulated by a single step reconfigurable mesh with maximum size that is polynomial in the size of the original mesh. The proof is constructive, where the construction of the single step RN-MESH holds for the relatively weak undirected RN-MESH model. In this model broadcasts made on buses arrive at all nodes that belong to the undirected connected component of the transmitting processor. A result similar to the one that is obtained in this work was previously obtained for the directed reconfigurable mesh model (DRN) (Ben-Asher and Schuster, 1996). However, the construction for the DRN-MESH relies on the fact that the buses are directed, and thus cannot be applied to the undirected case. In addition, the construction presented is simpler and uses significantly fewer processors than the one obtained for the DRN-MESH.

ParC is an extension of the C programming language with block-oriented parallel constructs that allow the programmer to express fine-grain parallelism in a shared-memory model. It is suitable for the expression of parallel shared-memory algorithms, and also conducive for the parallelization of sequential C programs. In addition, performance enhancing transformations can be applied within the language, without resorting to low-level programming. The language includes closed constructs to create parallelism, as well as instructions to cause the termination of parallel activities and to enforce synchronization. The parallel constructs are used to define the scope of shared variables, and also to delimit the sets of activities that are influenced by termination or synchronization instructions. The semantics of parallelism are discussed, especially relating to the discrepancy between the limited number of physical processors and the potentially much larger number of parallel activities in a program.

This paper studies a set of basic algorithms for SIMD Perfect Shuffle networks. These algorithms where studied in several papers, but for the 1-D case, where the size of the problem N is the same as the number of processors P. For the 2-D case of N = L * P, studied by [GK-80] and [Kr-81], we improve several algorithms, achieving run time Ο(L + log P) rather than Ο(L * log P), as N exceeds P. We give non-trivial algorithms for the following 2-D operations: Row-Reduction, Parallel-Prefix, Transpose, Smoothing and Cartesian-Product.