waashk/dblp huggingface dataset:
hiding communication latency and coherence overhead in software dsms. in this paper we propose the use of a pci-based programmable protocol controller for hiding communication and coherence overheads in software dsms. our protocol controller provides three different types of overhead tolerance: a) moving basic communication and coherence tasks away from computation processors; b) prefetching of diffs; and c) generating and applying diffs with hardware assistance. we evaluate the isolated and combined impact of these features on the performance of treadmarks. we also compare performance against two versions of the shrimp-based aurc protocol. using detailed execution-driven simulations of a 16-node network of workstations, we show that the greatest performance benefits provided by our protocol controller come from our hardware-supported diffs. reducing the burden of communication and coherence transactions on the computation processor is also beneficial but to a smaller extent. prefetching is not always profitable. our results show that our protocol controller can improve running time performance by up to 50% for treadmarks, which means that it can double the treadmarks speedups. the overlapping implementation of treadmarks performs as well or better than aurc for 5 of our 6 applications. we conclude that the simple hardware support we propose allows for the implementation of high-performance software dsms at low cost. based on this conclusion, we are building the ncp2 parallel system at coppe/ufrj.
efficent synchronization primitives for large-scale cache-coherent multiprocessors. this paper proposes a set of efficient primitives for process synchronization in multiprocessors. the only assumptions made in developing the set of primitives are that hardware combining is not implemented in the inter-connect, and (in one case) that the interconnect supports broadcast. the primitives make use of synchronization bits (syncbits) to provide a simple mechanism for mutual exclusion. the proposed implementation of the primitives includes efficient (i.e. local) busy-waiting for syncbits. in addition, a hardware-supported mechanism for maintaining a first-come first-serve queue of requests for a syncbit is proposed. this queueing mechanism allows for a very efficient implementation of, as well as fair access to, binary semaphores. we also propose to implement fetch and add with combining in software rather than hardware. this allows an architecture to scale to a large number of processors while avoiding the cost of hardware combining. scenarios for common synchronization events such as work queues and barriers are presented to demonstrate the generality and ease of use of the proposed primitives. the efficient implementation of the primitives is simpler if the multiprocessor has a hardware cache-consistency protocol. to illustrate this point, we outline how the primitives would be implemented in the multicube multiprocessor [gowo88].
architectural support for multilanguage parallel programming on heterogeneous systems. we have designed and implemented a software facility, called agora, that supports the development of parallel applications written in multiple languages. at the core of agora there is a mechanism that allows concurrent computations to share data structures independently of the computer architecture they are executed on. concurrent computations exchange control information by using a pattern-directed technique. this paper describes the agora shared memory and its software implementation on both tightly and loosely-coupled architectures.
a stream compiler for communication-exposed architectures. with the increasing miniaturization of transistors, wire delays are becoming a dominant factor in microprocessor performance. to address this issue, a number of emerging architectures contain replicated processing units with software-exposed communication between one unit and another (e.g., raw, smartmemories, trips). however, for their use to be widespread, it will be necessary to develop compiler technology that enables a portable, high-level language to execute efficiently across a range of wire-exposed architectures.in this paper, we describe our compiler for streamit: a high-level, architecture-independent language for streaming applications. we focus on our backend for the raw processor. though streamit exposes the parallelism and communication patterns of stream programs, some analysis is needed to adapt a stream program to a software-exposed processor. we describe a partitioning algorithm that employs fission and fusion transformations to adjust the granularity of a stream graph, a layout algorithm that maps a stream graph to a given network topology, and a scheduling strategy that generates a fine-grained static communication pattern for each computational element.we have implemented a fully functional compiler that parallelizes streamit applications for raw, including several load-balancing transformations. using the cycle-accurate raw simulator, we demonstrate that the streamit compiler can automatically map a high-level stream abstraction to raw without losing performance. we consider this work to be a first step towards a portable programming model for communication-exposed architectures.
whole-program optimization for time and space efficient threads. modern languages and operating systems often encourage programmers to use threads, or independent control streams, to mask the overhead of some operations and simplify program structure. multitasking operating systems use threads to mask communication latency, either with hardwares devices or users. client-server applications typically use threads to simplify the complex control-flow that arises when multiple clients are used. recently, the scientific computing community has started using threads to mask network communication latency in massively parallel architectures, allowing computation and communication to be overlapped. lastly, some architectures implement threads in hardware, using those threads to tolerate memory latency.in general, it would be desirable if threaded programs could be written to expose the largest degree of parallelism possible, or to simplify the program design. however, threads incur time and space overheads, and programmers often compromise simple designs for performance. in this paper, we show how to reduce time and space thread overhead using control flow and register liveness information inferred after compilation. our techniques work on binaries, are not specific to a particular compiler or thread library and reduce the the overall execution time of fine-grain threaded programs by &asymp; 15-30%. we use execution-driven analysis and an instrumented operating system to show why the execution time is reduced and to indicate areas for future work.
software profiling for hot path prediction: less is more. recently, there has been a growing interest in exploiting profile information in adaptive systems such as just-in-time compilers, dynamic optimizers and, binary translators. in this paper, we show that sophisticated software profiling schemes that provide highly accurate information in an offline setting are ill-suited for these dynamic code generation systems. we experimentally demonstrate that hot path predictions must be made early in order to control the rising cost of missed opportunity that result from the prediction delay. we also show that existing sophisticated path profiling schemes, if used in an online setting, offer no prediction advantages over simpler schemes that exhibit much lower runtime overheads.based on these observation we developed a new low-overhead software profiling scheme for hot path prediction. using an abstract metric we compare our scheme to path profile based prediction and show that our scheme achieves comparable prediction quality. in our second set of experiments we include runtime overhead and evaluate the performance of our scheme in a realistic application: dynamo, a dynamic optimization system. the results show that our prediction scheme clearly outperforms path profile based prediction and thus confirm that less profiling as exhibited in our scheme will actually lead to more effective hot path prediction.
riscs versus ciscs for prolog: a case study. this paper compares the performance of executing compiled prolog code on two different architectures under development at u. c. berkeley. the first is the plm, a special-purpose cisc architecture intended as a coprocessor for a host machine. the second is spur, a general-purpose risc architecture that supports tagged data. fourteen standard benchmark programs were run on both the plm and spur simulators. the compiled code for spur was obtained by simple macro-expansion of plm code generated by the plm prolog compiler. the two implementations are compared with regard to static and dynamic program size, execution speed, and memory system performance. on average, the macrocoded spur implementation has a static code size 14 times larger than the plm, executes 16 times more instructions, yet requires only 2.3 times the number of machine cycles (or has the performance of 0.43 plms). when memory system performance is taken into account, spur is equivalent to 0.29 plms. optimizations of the macro-expanded code and minor architectural changes to spur would increase this ratio to 0.53, or 0.60 for the largest benchmarks. thus a tagged risc architecture can execute prolog at least half as fast as a special-purpose cisc architecture for prolog.
the fuzzy barrier: a mechanism for high speed synchronization of processors. parallel programs are commonly written using barriers to synchronize parallel processes. upon reaching a barrier, a processor must stall until all participating processors reach the barrier. a software implementation of the barrier mechanism using shared variables has two major drawbacks. firstly, the execution of the barrier may be slow as it may not only require execution of several instructions and but also result in hot-spot accesses. secondly, processors that are stalled waiting for other processors to reach the barrier are essentially idling and cannot do any useful work. in this paper, the notion of the fuzzy barrier is presented, that avoids the above drawbacks. the first problem is avoided by implementing the mechanism in hardware. the second problem is solved by extending the barrier concept to include a region of statements that can be executed by a processor while it awaits synchronization. the barrier regions are constructed by a compiler and consist of several instructions such that a processor is ready to synchronize upon reaching the first instruction in this region and must synchronize before exiting the region. when synchronization does occur, the processors could be executing at any point in their respective barrier regions. the larger the barrier region, the more likely it is that none of the processors will have to stall. preliminary investigations show that barrier regions can be large and the use of program transformations can significantly increase their size. examples of situations where such a mechanism can result in improved performance are presented. results based on a software implementation of the fuzzy barrier on the encore multiprocessor indicate that the synchronization overhead can be greatly reduced using the mechanism.
compiler-controlled memory. optimizations aimed at reducing the impact of memory operations on execution speed have long concentrated on improving cache performance. these efforts achieve a. reasonable level of success. the primary limit on the compiler's ability to improve memory behavior is its imperfect knowledge about the run-time behavior of the program. the compiler cannot completely predict runtime access patterns.there is an exception to this rule. during the register allocation phase, the compiler often must insert substantial amounts of spill code; that is, instructions that move values from registers to memory and back again. because the compiler itself inserts these memory instructions, it has more knowledge about them than other memory operations in the program.spill-code operations are disjoint from the memory manipulations required by the semantics of the program being compiled, and, indeed, the two can interfere in the cache. this paper proposes a hardware solution to the problem of increased spill costs---a small compiler-controlled memory (ccm) to hold spilled values. this small random-access memory can (and should) be placed in a distinct address space from the main memory hierarchy. the compiler can target spill instructions to use the ccm, moving most compiler-inserted memory traffic out of the pathway to main memory and eliminating any impact that those spill instructions would have on the state of the main memory hierarchy. such memories already exist on some dsp microprocessors. our techniques can be applied directly on those chips.this paper presents two compiler-based methods to exploit such a memory, along with experimental results showing that speedups from using ccm may be sizable. it shows that using the register allocation's coloring paradigm to assign spilled values to memory can greatly reduce the amount of memory required by a program.
application-level checkpointing for shared memory programs. trends in high-performance computing are making it necessary for long-running applications to tolerate hardware faults. the most commonly used approach is checkpoint and restart (cpr) - the state of the computation is saved periodically on disk, and when a failure occurs, the computation is restarted from the last saved state. at present, it is the responsibility of the programmer to instrument applications for cpr.our group is investigating the use of compiler technology to instrument codes to make them self-checkpointing and self-restarting, thereby providing an automatic solution to the problem of making long-running scientific applications resilient to hardware faults. our previous work focused on message-passing programs.in this paper, we describe such a system for shared-memory programs running on symmetric multiprocessors. this system has two components: (i) a pre-compiler for source-to-source modification of applications, and (ii) a runtime system that implements a protocol for coordinating cpr among the threads of the parallel application. for the sake of concreteness, we focus on a non-trivial subset of openmp that includes barriers and locks.one of the advantages of this approach is that the ability to tolerate faults becomes embedded within the application itself, so applications become self-checkpointing and self-restarting on any platform. we demonstrate this by showing that our transformed benchmarks can checkpoint and restart on three different platforms (windows/x86, linux/x86, and tru64/alpha). our experiments show that the overhead introduced by this approach is usually quite small; they also suggest ways in which the current implementation can be tuned to reduced overheads further.
spatial computation. this paper describes a computer architecture, spatial computation (sc), which is based on the translation of high-level language programs directly into hardware structures. sc program implementations are completely distributed, with no centralized control. sc circuits are optimized for wires at the expense of computation units.in this paper we investigate a particular implementation of sc: ash (application-specific hardware). under the assumption that computation is cheaper than communication, ash replicates computation units to simplify interconnect, building a system which uses very simple, completely dedicated communication channels. as a consequence, communication on the datapath never requires arbitration; the only arbitration required is for accessing memory. ash relies on very simple hardware primitives, using no associative structures, no multiported register files, no scheduling logic, no broadcast, and no clocks. as a consequence, ash hardware is fast and extremely power efficient.in this work we demonstrate three features of ash: (1) that such architectures can be built by automatic compilation of c programs; (2) that distributed computation is in some respects fundamentally different from monolithic superscalar processors; and (3) that asic implementations of ash use three orders of magnitude less energy compared to high-end superscalar processors, while being on average only 33% slower in performance (3.5x worst-case).
programming with transactional coherence and consistency (tcc). transactional coherence and consistency (tcc) offers a way to simplify parallel programming by executing all code within transactions. in tcc systems, transactions serve as the fundamental unit of parallel work, communication and coherence. as each transaction completes, it writes all of its newly produced state to shared memory atomically, while restarting other processors that have speculatively read stale data. with this mechanism, a tcc-based system automatically handles data synchronization correctly, without programmer intervention. to gain the benefits of tcc, programs must be decomposed into transactions. we describe two basic programming language constructs for decomposing programs into transactions, a loop conversion syntax and a general transaction-forking mechanism. with these constructs, writing correct parallel programs requires only small, incremental changes to correct sequential programs. the performance of these programs may then easily be optimized, based on feedback from real program execution, using a few simple techniques.
compiler-directed page coloring for multiprocessors. this paper presents a new technique, compiler-directed page coloring, that eliminates conflict misses in multiprocessor applications. it enables applications to make better use of the increased aggregate cache size available in a multiprocessor. this technique uses the compiler's knowledge of the access patterns of the parallelized applications to direct the operating system's virtual memory page mapping strategy. we demonstrate that this technique can lead to significant performance improvements over two commonly used page mapping strategies for machines with either direct-mapped or two-way set-associative caches. we also show that it is complementary to latency-hiding techniques such as prefetching.we implemented compiler-directed page coloring in the suif parallelizing compiler and on two commercial operating systems. we applied the technique to the spec95fp benchmark suite, a representative set of numeric programs. we used the simos machine simulator to analyze the applications and isolate their performance bottlenecks. we also validated these results on a real machine, an eight-processor 350mhz digital alphaserver. compiler-directed page coloring leads to significant performance improvements for several applications. overall, our technique improves the spec95fp rating for eight processors by 8% over digital unix's page mapping policy and by 20% over a page coloring, a standard page mapping policy. the suif compiler achieves a spec95fp ratio of 57.4, the highest ratio to date.
data speculation support for a chip multiprocessor. thread-level speculation is a technique that enables parallel execution of sequential applications on a multiprocessor. this paper describes the complete implementation of the support for threadlevel speculation on the hydra chip multiprocessor (cmp). the support consists of a number of software speculation control handlers and modifications to the shared secondary cache memory system of the cmp this support is evaluated using five representative integer applications. our results show that the speculative support is only able to improve performance when there is a substantial amount of medium--grained loop-level parallelism in the application. when the granularity of parallelism is too small or there is little inherent parallelism in the application, the overhead of the software handlers overwhelms any potential performance benefits from speculative-thread parallelism. overall, thread-level speculation still appears to be a promising approach for expanding the class of applications that can be automatically parallelized, but more hardware intensive implementations for managing speculation control are required to achieve performance improvements on a wide class of integer applications.
architectural support for fast symmetric-key cryptography. the emergence of the internet as a trusted medium for commerce and communication has made cryptography an essential component of modern information systems. cryptography provides the mechanisms necessary to implement accountability, accuracy, and confidentiality in communication. as demands for secure communication bandwidth grow, efficient cryptographic processing will become increasingly vital to good system performance.in this paper, we explore techinques to improve the performance of symmetric key cipher algorithms. eight popular strong encryption algorithms are examined in detail. analysis reveals the algorithms are computaionally complex and contain little parallelism. overall throughput on high-end microprocessor is quite poor, a 600 mhz processor is incapable of saturation a t3 communication line with 3des (triple des) encrypted data.we introduce new instructions taht improve the efficiency of the analyzed algorithms. our approach adds instruction set support for fast substitutions, general permutations, rotates, and modular arithmetic. performance analysis of the optimized ciphers shows an overall speedup of 59% over a baseline machine with rotate instructions and 74% speedup over a baseline without rotates. even higher speedups are demonstrated with optimized subtitutions (sboxes) and additional functional unit resources. our analyses of the original and optimized algorithms suggest future directions for the design of high-performance programmable cryptographic processors.
an architectural alternative to optimizing compilers. programming languages are designed to make programming productive. computer architectures are designed to make program execution efficient. although architectures should be designed with programming languages in mind, it may be as inappropriate to make the computer execute the programming language directly it is to make the programmer use machine language. it is the compiler's job to match the programming language and the computer architectures, and therefore making compiler's efficient and easy to write are important design goals of a complete hardware/software system. this paper summerizes research completed in 1980 [5] on a computer architecture, tm, that takes over some of the more burdensome tasks of optimizing compilers for high-level-languages (hll's), performing these tasks dynamically during the execution of the object program. this is a different approach to making compilers efficient than is commonly taken; more common approaches include devising more efficient optimization algorithms[i], being clever about when to do optimizations [4], and building the compilers semiautomatically [6].
architectural support for synchronous task communication. this paper describes the motivation for a set of intertask communication primitives, the hardware support of these primitives, the architecture used in the sylvan project which studies these issues, and the experience gained from various experiments conducted in this area. we start by describing how these facilities have been implemented in a multiprocessor configuration that utilizes a shared backplane. this configuration represents a single node in the system. the latter part of the paper discusses a distributed multiple node system and the extension of the primitives that are used in this expanded environment. this research is funded by a strategic grant from the natural sciences and engineering research council of canada (grant no. g1581).