waashk/dblp huggingface dataset:
an integrated compile-time/run-time software distributed shared memory system. on a distributed memory machine, hand-coded message passing leads to the most efficient execution, but it is difficult to use. parallelizing compilers can approach the performance of hand-coded message passing by translating data-parallel programs into message passing programs, but efficient execution is limited to those programs for which precise analysis can be carried out. shared memory is easier to program than message passing and its domain is not constrained by the limitations of parallelizing compilers, but it lags in performance. our goal is to close that performance gap while retaining the benefits of shared memory. in other words, our goal is (1) to make shared memory as efficient as message passing, whether hand-coded or compiler-generated, (2) to retain its ease of programming, and (3) to retain the broader class of applications it supports.to this end we have designed and implemented an integrated compile-time and run-time software dsm system. the programming model remains identical to the original pure run-time dsm system. no user intervention is required to obtain the benefits of our system. the compiler computes data access patterns for the individual processors. it then performs a source-to-source transformation, inserting in the program calls to inform the run-time system of the computed data access patterns. the run-time system uses this information to aggregate communication, to aggregate data and synchronization into a single message, to eliminate consistency overhead, and to replace global synchronization with point-to-point synchronization wherever possible.we extended the parascope programming environment to perform the required analysis, and we augmented the treadmarks run-time dsm library to take advantage of the analysis. we used six fortran programs to assess the performance benefits: jacobi, 3d-fft, integer sort, shallow, gauss, and modified gramm-schmidt, each with two different data set sizes. the experiments were run on an 8-node ibm sp/2 using user-space communication. compiler optimization in conjunction with the augmented run-time system achieves substantial execution time improvements in comparison to the base treadmarks, ranging from 4% to 59% on 8 processors. relative to message passing implementations of the same applications, the compile-time run-time system is 0-29% slower than message passing, while the base run-time system is 5-212% slower. for the five programs that xhpf could parallelize (all except is), the execution times achieved by the compiler optimized shared memory programs are within 9% of xhpf.
efficient and flexible value sampling. this paper presents novel sampling-based techniques for collecting statistical profiles of register contents, data values, and other information associated with instructions, such as memory latencies. values of interest are sampled in response to periodic interrupts. the resulting value profiles can be analyzed by programmers and optimizers to improve the performance of production uniprocessor and multiprocessor systems.our value sampling system extends the dcpi continuous profiling infrastructure, and inherits many of its desirable properties: our value profiler has low overhead (approximately 10% slowdown); it profiles all the code in the system, including the operating system kernel; and it operates transparently, without requiring any modifications to the profiled code.
application-controlled physical memory using external page-cache management. next generation computer systems will have gigabytes of physical memory and processors in the 100 mips range or higher. contrary to some conjectures, this trend requires more sophisticated memory management support for memory-bound computations such as scientific simulations and systems such as large-scale database systems, even though memory management for most programs will be less of a concern. we describe the design, implementation and evaluation of a virtual memory system that provides application control of physical memory using external page-cache management. in this approach, a sophisticated application is able to monitor and control the amount of physical memory it has available for execution, the exact contents of this memory, and the scheduling and nature of page-in and page-out using the abstraction of a physical page cache provided by the kernel. we claim that this approach can significantly improve performance for many memory-bound applications while reducing kernel complexity, yet does not complicate other applications or reduce their performance.
low-overhead memory leak detection using adaptive statistical profiling. sampling has been successfully used to identify performance optimization opportunities. we would like to apply similar techniques to check program correctness. unfortunately, sampling provides poor coverage of infrequently executed code, where bugs often lurk. we describe an adaptive profiling scheme that addresses this by sampling executions of code segments at a rate inversely proportional to their execution frequency. to validate our ideas, we have implemented swat, a novel memory leak detection tool. swat traces program allocations/ frees to construct a heap model and uses our adaptive profiling infrastructure to monitor loads/stores to these objects with low overhead. swat reports 'stale' objects that have not been accessed for a 'long' time as leaks. this allows it to find all leaks that manifest during the current program execution. since swat has low runtime overhead (‹5%), and low space overhead (‹10% in most cases and often less than 5%), it can be used to track leaks in production code that take days to manifest. in addition to identifying the allocations that leak memory, swat exposes where the program last accessed the leaked data, which facilitates debugging and fixing the leak. swat has been used by several product groups at microsoft for the past 18 months and has proved effective at detecting leaks with a low false positive rate (‹10%).
compiling smalltalk-80 to a risc. the smalltalk on a risc project at u. c. berkeley proves that a high-level object-oriented language can attain high performance on a modified reduced instruction set architecture. the single most important optimization is the removal of a layer of interpretation, compiling the bytecoded virtual machine instructions into low-level, register-based, hardware instructions. this paper describes the compiler and how it was affected by soar architectural features. the compiler generates code of reasonable density and speed. because of smalltalk-80's semantics, relatively few optimizations are possible, but hardware and software mechanisms at runtime offset these limitations. register allocation for an architecture with register windows comprises the major task of the compiler. performance analysis suggests that soar is not simple enough; several hardware features could be efficiently replaced by instruction sequences constructed by the compiler.
ap1000+: architectural support of put/get interface for parallelizing compiler. the scalability of distributed-memory parallel computers makes them attractive candidates for solving large-scale problems. new languages, such as hpf, fortrand, and vpp fortran, have been developed to enable existing software to be easily ported to such machines. many distributed-memory parallel computers have been built, but none of them support the mechanisms required by such languages. we studied the mechanisms required by parallelizing compilers and proposed a new architecture to support them. based on this proposed architecture, we developed a new distributed-memory parallel computer, the ap1000+, which is an enhanced version of the ap1000. using scientific applications in vpp fortran and c, such as nas parallel benchmarks, we simulated the performance of the ap1000+.
dynamic dead-instruction detection and elimination. we observe a non-negligible fraction--3 to 16% in our benchmarks--of dynamically dead instructions, dynamic instruction instances that generate unused results. the majority of these instructions arise from static instructions that also produce useful results. we find that compiler optimization (specifically instruction scheduling) creates a significant portion of these partially dead static instructions. we show that most of the dynamically instructions arise from a small set of static instructions that produce dead values most of the time.we leverage this locality by proposing a dead instruction predictor and presenting a scheme to avoid the execution of predicted-dead instructions. our predictor achieves an accuracy of 93% while identifying over 91% of the dead instructions using less than 5 kb of state. we achieve such high accuracies by leveraging future control flow information (i.e., branch predictions) to distinguish between useless and useful instances of the same static instruction.we then present a mechanism to avoid the register allocation, instruction scheduling, and execution of predicted dead instructions. we measure reductions in resource utilization averaging over 5% and sometimes exceeding 10%, covering physical register management (allocation and freeing), register file read and write traffic, and data cache accesses. performance improves by an average of 3.6% on an architecture exhibiting resource contention. additionally, our scheme frees future compilers from the need to consider the costs of dead instructions, enabling more aggressive code motion and optimization. simultaneously, it mitigates the need for good path profiling information in making inter-block code motion decisions.
an architecture for the direct execution of the forth programming language. we have developed a simple direct execution architecture for a 32 bit forth microprocessor. the processor can directly access a linear address space of over 4 gigawords. two instruction types are defined; a subroutine call, and a user defined microcode instruction. on-chip stack caches allow most forth primitives to execute in a single cycle.
reducing branch costs via branch alignment. several researchers have proposed algorithms for basic block reordering. we call these branch alignment algorithms. the primary emphasis of these algorithms has been on improving instruction cache locality, and the few studies concerned with branch prediction reported small or minimal improvements. as wide-issue architectures become increasingly popular the importance of reducing branch costs will increase, and branch alignment is one mechanism which can effectively reduce these costs.in this paper, we propose an improved branch alignment algorithm that takes into consideration the architectural cost model and the branch prediction architecture when performing the basic block reordering. we show that branch alignment algorithms can improve a broad range of static and dynamic branch prediction architectures. we also show that a program performance can be improved by approximately 5% even when using recently proposed, highly accurate branch prediction architectures. the programs are compiled by any existing compiler and then transformed via binary transformations. when implementing these algorithms on a alpha axp 21604 up to a 16% reduction in total execution time is achieved.
integration of message passing and shared memory in the stanford flash multiprocessor. the advantages of using message passing over shared memory for certain types of communication and synchronization have provided an incentive to integrate both models within a single architecture. a key goal of the flash (flexible architecture for shared memory) project at stanford is to achieve this integration while maintaining a simple and efficient design. this paper presents the hardware and software mechanisms in flash to support various message passing protocols. we achieve low overhead message passing by delegating protocol functionality to the programmable node controllers in flash and by providing direct user-level access to this messaging subsystem. in contrast to most earlier work, we provide an integrated solution that handles the interaction of the messaging protocols with virtual memory, protected multiprogramming, and cache coherence. detailed simulation studies indicate that this system can sustain message-transfers rates of several hundred megabytes per second, effectively utilizing projected network bandwidths for next generation multiprocessors.
cache-conscious data placement. as the gap between memory and processor speeds continues to widen, cache eficiency is an increasingly important component of processor performance. compiler techniques have been used to improve instruction cache pet$ormance by mapping code with temporal locality to different cache blocks in the virtual address space eliminating cache conflicts. these code placement techniques can be applied directly to the problem of placing data for improved data cache pedormance.in this paper we present a general framework for cache conscious data placement. this is a compiler directed approach that creates an address placement for the stack (local variables), global variables, heap objects, and constants in order to reduce data cache misses. the placement of data objects is guided by a temporal relationship graph between objects generated via profiling. our results show that profile driven data placement significantly reduces the data miss rate by 24% on average.
hardware/software tradeoffs for increased performance. most new computer architectures are concerned with maximizing performance by providing suitable instruction sets for compiled code and providing support for systems functions. we argue that the most effective design methodology must make simultaneous tradeoffs across all three areas: hardware, software support, and systems support. recent trends lean towards extensive hardware support for both the compiler and operating systems software. however, consideration of all possible design tradeoffs may often lead to less hardware support. several examples of this approach are presented, including: omission of condition codes, word-addressed machines, and imposing pipeline interlocks in software. the specifics and performance of these approaches are examined with respect to the mips processor.
cheap hardware support for software debugging and profiling. we wish to determine the effectiveness of some simple hardware for debugging and profiling compiled programs on a conventional processor. the hardware cost is small -- a counter decremented on each instruction that raises an exception when its value becomes zero. with the counter a debugger can provide data watchpoints and reverse execution: a profiler can measure the total instruction cost of a code segment and sample the program counter accurately. such a counter has been included on a single-board mc68020 workstation, for which system software is currently being written. we will report our progress at the symposium.
compiler optimizations for improving data locality. in the past decade, processor speed has become significantly faster than memory speed. small, fast cache memories are designed to overcome this discrepancy, but they are only effective when programs exhibit data locality. in this paper, we present compiler optimizations to improve data locality based on a simple yet accurate cost model. the model computes both temporal and spatial reuse of cache lines to find desirable loop organizations. the cost model drives the application of compound transformations consisting of loop permutation, loop fusion, loop distribution, and loop reversal. we demonstrate that these program transformations are useful for optimizing many programs.to validate our optimization strategy, we implemented our algorithms and ran experiments on a large collection of scientific programs and kernels. experiments with kernels illustrate that our model and algorithm can select and achieve the best performance. for over thirty complete applications, we executed the original and transformed versions and simulated cache hit rates. we collected statistics about the inherent characteristics of these programs and our ability to improve their data locality. to our knowledge, these studies are the first of such breadth and depth. we found performance improvements were difficult to achieve because benchmark programs typically have high hit rates even for small data caches; however, our optimizations significantly improved several programs.
system architecture directions for networked sensors. technological progress in integrated, low-power, cmos communication devices and sensors makes a rich design space of networked sensors viable. they can be deeply embedded in the physical world and spread throughout our environment like smart dust. the missing elements are an overall system architecture and a methodology for systematic advance. to this end, we identify key requirements, develop a small device that is representative of the class, design a tiny event-driven operating system, and show that it provides support for efficient modularity and concurrency-intensive operation. our operating system fits in 178 bytes of memory, propagates events in the time it takes to copy 1.25 bytes of memory, context switches in the time it takes to copy 6 bytes of memory and supports two level scheduling. the analysis lays a groundwork for future architectural advances.
hardware support for fast capability-based addressing. traditional methods of providing protection in memory systems do so at the cost of increased context switch time and/or increased storage to record access permissions for processes. with the advent of computers that supported cycle-by-cycle multithreading, protection schemes that increase the time to perform a context switch are unacceptable, but protecting unrelated processes from each other is still necessary if such machines are to be used in non-trusting environments.this paper examines guarded pointers, a hardware technique which uses tagged 64-bit pointer objects to implement capability-based addressing. guarded pointers encode a segment descriptor into the upper bits of every pointer, eliminating the indirection and related performance penalties associated with traditional implementations of capabilities. all processes share a single 54-bit virtual address space, and access is limited to the data that can be referenced through the pointers that a process has been issued. only one level of address translation is required to perform a memory reference. sharing data between processes is efficient, and protection states are defined to allow fast protected subsystem calls and create unforgeable data keys.
reference history, page size, and migration daemons in local/remote architectures. we address the problem of paged main memory management in the local/remote architecture subclass of shared memory multiprocessors. we consider the case where the operating system has primary responsibility and uses page migration as its main tool. we identify some of the key issues with respect to architectural support (reference history maintenance, and page size), and operating system mechanism (duration between daemon passes, and number of migration daemons). the experiments were conducted using software implemented page tables on 32-node bbn butterfly plus&trade;. several numeral programs with both synthetic and real data were used as the workload. the primary conclusion is that for the cases considered migration was at best marginally effective. on the other hand, practical migration mechanisms were robust and never significantly degraded performance. the specific results include: 1) referenced bits with aging can closely approximate usage fields, 2) larger page sizes are beneficial except when the page is large enough to include locality sets of two processes, and 3) multiple migration daemons can be useful. only small regions of the space of architectural, system, and workload parameters were explored. further investigation of other parameter combinations is clearly warranted.
limitless directories: a scalable cache coherence scheme. caches enhance the performance of multiprocessors by reducing network traffic and average memory access latency. however, cache-based systems must address the problem of cache coherence. we propose the limitless directory protocol to solve this problem. the limitless scheme uses a combination of hardware and software techniques to realize the performance of a full-map directory with the memory overhead of a limited directory. this protocol is supported by alewife, a large-scale multiprocessor. we describe the architectural interfaces needed to implement the limitless directory, and evaluate its performance through simulations of the alewife machine.
the intrinsic bandwidth requirements of ordinary programs. while there has been an abundance of recent papers on hardware and software approaches to improving the performance of memory accesses, few papers have addressed the problem from the program's point of view. there is a general notion that certain programs have larger working sets than others. however, there is no quantitative method for evaluating and comparing the memory requirements of programs.this paper introduces the bandwidth spectrum for characterizing the memory requirements of a program's instruction and data stream. the bandwidth spectrum measures the average bandwidth requirement of a program as a function of available local memory. these measurements are performed under the most idealized conditions of perfect knowledge and perfect memory management. as such, they represent the lower bounds on the memory requirements of programs. we present the bandwidth spectrums for a set of 22 benchmarks and show how they can be used in the comparison of memory requirements and i/o requirement. the bandwidth spectrums also offer a convenient method to weigh the trade-off amongst instruction issue rate, local memory capacity and bandwidth into local memory.using the bandwidth spectrum, we show that at issue rates of four or less, bandwidth usually scales linearly with the issue rate. at higher issue rates, bandwidth can often scale superlinearly with respect to issue rate. finally, we also investigate the effects of varying the input sets on the bandwidth spectrums.
scheduling and page migration for multiprocessor compute servers. several cache-coherent shared-memory multiprocessors have been developed that are scalable and offer a very tight coupling between the processing resources. they are therefore quite attractive for use as compute servers for multiprogramming and parallel application workloads. process scheduling and memory management, however, remain challenging due to the distributed main memory found on such machines. this paper examines the effects of os scheduling and page migration policies on the performance of such compute servers. our experiments are done on the stanford dash, a distributed-memory cache-coherent multiprocessor. we show that for our multiprogramming workloads consisting of sequential jobs, the traditional unix scheduling policy does very poorly. in contrast, a policy incorporating cluster and cache affinity along with a simple page-migration algorithm offers up to two-fold performance improvement. for our workloads consisting of multiple parallel applications, we compare space-sharing policies that divide the processors among the applications to time-slicing policies such as standard unix or gang scheduling. we show that space-sharing policies can achieve better processor utilization due to the operating point effect, but time-slicing policies benefit strongly from user-level data distribution. our initial experience with automatic page migration suggests that policies based only on tlb miss information can be quite effective, and useful for addressing the data distribution problems of space-sharing schedulers.