waashk/acm huggingface dataset:
loop transformations for architectures with partitioned register banks  embedded systems require maximum performance from a processor within significant constraints in power consumption and chip cost. using software pipelining, processors can often exploit considerable instruction-level parallelism (ilp), and thus significantly improve performance, at the cost of substantially increasing register requirements. these increasing register requirements, however, make it difficult to build a high-performance embedded processor with a single, multi-ported register file while maintaining clock speed and limiting power consumption.  some digital signal processors, such as the ti c6x, reduce the number of ports required for a register bank by partitioning the register bank into multiple banks. disjoint subsets of functional units are directly connected to one of the partitioned register banks. each register bank and its associate functional units is called a _cluster_. clustering reduces the number of ports needed on a per-bank basis, allowing an increased clock rate. however, execution speed can be hampered because of the potential need to copy "non- local" operands among register banks in order to make them available to the functional unit performing an operation. the task of the compiler is to both maximize parallelism and minimize the number of remote register accesses needed.  previous work has concentrated on methods to partition virtual registers amongst the target architecture's clusters. in this paper, we show how high- level loop transformations can enhance the partitioning obtained by low-level schemes. in our experiments, loop transformations improved software pipelining by 27% on a machine with 2 clusters, each having 1 floating-point and 1 integer register bank and 4 functional units. we also observed a 20% improvement on a similar machine with 4 clusters of 2 functional units. in fact, by performing the described loop transformations we were able to show improvements of greater than 10% over schedules (for un-transformed loops) generated with the unrealistic assumption of a single multi-ported register bank.  xianglong huang steve carr philip sweany
automated testing in apl - an application of exception handling  several apl systems have recently been enhanced to include exception handling facilities. the construction of an automated tester is presented as a case study of one such definition: the latent expression exception handling system [1] available on stsc's apl*plus@@@@ system.  the automated tester was developed as a tool to manage the systematic verification of apl system features through programmed tests. a test is an apl program containing assertions that prescribe the outcome of associated statements. the tester verifies that the asserted outcomes are in fact realized during execution.  this paper describes the central role of exception handling in the implementation of the automated tester. when tests are executed as apl programs, the exceptions generated by the assertion construct can be used to control interpretation of the assertion. other errors encountered during test execution must be intercepted and recorded, so that it is possible to assert that a statement results in an error. finally, since the tester should execute large sets of tests unattended, it should not be interrupted by improper tests or unexpected results.  jan f. prins
visualizing unix synchronization operations the synchronization of concurrent tasks is a fundamental topic in computer science education. graphical tools that visualize the effects of synchronization operations are helpful to understand their effects and pitfalls. _paco_ and _andi_ are one such tool. c programs using unix system calls for process and semaphore management are instrumented by paco with specific output functions. when executing these programs, andi visualizes the effects of the system calls by a dynamic graphical output. carsten vogt
compiler techniques for maximizing fine-grain and coarse-grain parallelism in loops with uniform dependences  in this paper, an approach to the problem of exploiting parallelism within nested loops is proposed. the proposed method first finds out all the initially independent computations, and then, based on them, identifies the valid partitioning bases to partition the entire iteration space of the loop nest. because the shape of the iteration space is taken into account, pseudo- dependence relations are eliminated and hence more parallelism is exploited. our approach provides a systematic method to maximize the degree of fine- or coarse-grain parallelism and is free from the open question of how to combine different loop transformations for the goal of maximizing parallelism. it is also shown that our approach can exploit more parallelism than other related work and have many advantages over them.  yeong-sheng chen sheng-de wang chien-min wang
interface usage measurements in a user interface management system  user interface management systems have provided support for most user interface design personnel with the exception of dialogue evaluators. potential support that a uims can provide to evaluators of user interfaces generated by the uims are discussed. metrics for measuring interactive behavior have been implemented as part of a user interface management system. it is shown how the external control and separate dialogue description features of uimss make possible such measurements. these metrics are automatically mapped back to the responsible portions of the dialogue description. reports are generated which aid interface evaluators in locating specific problems in a user interface design.  dan r. olsen bradley w. halversen
operating systems specialization (invited talk) (abstract only): experiences, opportunities and challenges  this talk will present a systems-centric view of the opportunities, effectiveness, and challenges of applying specialization techniques to operating systems. the first part of the talk will focus on our experiences using manual and then tool-assisted specialization in the systematic optimization of legacy operating systems software. these experiences were gained in the synthetix project which explored the use of static, dynamic and incremental optimistic specialization in a variety of operating system contexts, including file system calls in hp- ux, linux signal delivery, berkeley packet filter processing, and sun rpc. the second part of the talk will focus on the lessons learned in synthetix, the implications for systems, and the key opportunities and challenges for future research.  jonathan walpole is a professor in the computer science and engineering department at oregon graduate institute. his research interests are in the area of adaptive systems software and its application in distributed, mobile, multimedia computing environments. his work has focused on quality of service specification, adaptive resource management and dynamic specialization for enhanced performance, survivability and evolvability of large software systems.  jonathan walpole
embedding continuations in procedural objects  continuations, when available as first-class objects, provide a general control abstraction in programming languages. they liberate the programmer from specific control structures, increasing programming language extensibility. such continuations may be extended by embedding them in procedural objects. this technique is first used to restore a fluid environment when a continuation object is invoked. we then consider techniques for constraining the power of continuations in the interest of security and efficiency. domain mechanisms, which create dynamic barriers for enclosing control, are implemented using fluids. domains are then used to implement an unwind-protect facility in the presence of first-class continuations. finally, we present two mechanisms, wind-unwind and dynamic-wind, that generalize unwind-protect.  christopher t. haynes daniel p. friedman
experience with a modular typed language: protel  the support for modular software and the ability to perform type checking across module boundaries are becoming the mainstay of recent high level language design. this is well illustrated by languages such as mesa and the us department of defence's new standard language ada. at bell-northern research, protel, one of the first modular typed languages, has been used since 1975 to implement a substantial software system. the experience accumulated in building this system has given us a unique perspective. it has shown that the confidence of language designers in modular typed languages is well founded. it has also revealed some pitfalls which others will undoubtedly encounter. the purpose of this paper is to share our experience by outlining the nature of the problems and our solutions to them.  p. m. cashin m. l. joliat r. f. kamel d. m. lasker
system object model (som) and ada: an example of corba at work  ibm's system object model (som) provides a powerful toolset for building object- oriented applications in multiple languages on multiple platforms. it is fully compliant with the object management group's (omg) common request broker architecture (corba). oc system' powada product allows ada95 programmers "first-class" access to som. this article describes the use of som classes to build a simple "groupware" application in ada95.  g. vincent castellano
hierarchical modularity  to cope with the complexity of very large systems, it is not sufficient to divide them into simple pieces because the pieces themselves will either be too numerous or too large. a hierarchical modular structure is the natural solution. in this article we explain how that approach can be applied to software. our compilation manager provides a language for specifying where individual modules fit into a hierarchy and how they are related semantically. we pay particular attention to the structure of the global name space of program identifiers that are used for module linkage because any potential for name clashes between otherwise unrelated parts of a program can negatively affect modularity. we discuss the theoretical issues in building software hierarchically, and we describe our implementation of cm, the compilation manager for standard ml of new jersey.  matthias blume andrew w. appel
safe: a semantic technique for transforming programs in the presence of errors  language designers and implementors have avoided specifying and preserving the meaning of programs that produce errors. this is apparently because being forced to preserve error behavior limits severely the scope of program optimization, even for correct programs. however, error behavior preservation is desirable for debugging, and error behavior must be preserved in any language that permits user-generated errors (i.e., exceptions).  this article presents a technique for expressing general program transformations for languages that possess a rich collection of distinguishable error values. this is accomplished by defining a higher-order function called safe, which can be used to annotate those portions of a program that are guaranteed not to produce errors. it is shown that this facilitates the expression of very general program transformations, effectively giving program transformations in a language with many error values the same power and generality as program transformations in a language with only a single error value.  using the semantic properties of safe, it is possible to provide some useful sufficient conditions for establishing the correctness of transformations in the presence of errors. in particular, a substitutability theorem is proven, which can be used to justify "in-context" optimizations: transformations that alter the meanings of subexpressions without changing the meaning of the whole program. finally, the effectiveness of the technique is demonstrated by some examples of its use in an optimizing compiler.  alexander aiken john h. williams edward l. wimmers
analysis of file i/o traces in commercial computing environments  improving the performance of the file system is becoming increasingly important to alleviate the effect of i/o bottlenecks in computer systems. to design changes to an existing file system or to architect a new file system it is important to understand current usage patterns. in this paper we analyze file i/o traces of several existing production computer sytems to understand file access behavior.  our analysis suggests that a relatively small percentage of the files are active. the amount of total data active is also quite small for interactive environments. an average file encounters a relatively small number of file opens while receiving an order of magnitude larger number of reads to it. an average process opens quite a large number of files over a typical prime time period. what is more significant is that the effect of outliers on many of the characteristics we studied is dominant. a relatively small number of processes dominate the activity, and a very small number of files receive most of these operations.  in addition, we provide a comprehensive analysis of the dynamic sharing of files in each of these enviroments, addressing both the simultaneous and sequential sharing aspects, and the activity to these shared files. we observe that although only a third of the active files are sequentially shared, they receive a very large proportion of the total operations. we analyze the traces from a given environment across different lengths of time, such as one hour, three hour and whole work-day intervals and do this for 3 different environments. this gives us an idea of the shortest length of the trace needed to have confidence in the estimation of the parameters.  k. k. ramakrishnan prabuddha biswas ramakrishna karedla
the spineless g-machine  recent developments in functional language implementations have resulted in the g-machine, a programmed graph-reduction machine. taking this as a basis, we introduce an optimised method of performing graph reduction, which does not need to build the spine of the expression being reduced. this spineless g-machine only updates shared expressions, and then only when they have been reduced to weak head normal form. it is thus more efficient than the standard method of performing graph reduction.  we begin by outlining the philosophy and key features of the spineless g-machine, and comparing it with the standard g-machine. simulation results for the two machines are then presented and discussed. the spineless g-machine is also compared with tim, giving a series of transformations by which they can be interconverted. these open up a wide design space for abstract graph reduction machines, which was previously unknown. a full specification of the spineless machine is given in the appendix, together with compilation rules for a simple functional language.  g. l. burn s. l. peyton jones j. d. robson
a new notation for arrows the categorical notion of monad, used by moggi to structure denotational descriptions, has proved to be a powerful tool for structuring combinator libraries. moreover, the monadic programming style provides a convenient syntax for many kinds of computation, so that each library defines a new sublanguage. recently, several workers have proposed a generalization of monads, called variously "arrows" or freyd-categories. the extra generality promises to increase the power, expressiveness and efficiency of the embedded approach, but does not mesh as well with the native abstraction and application. definitions are typically given in a point-free style, which is useful for proving general properties, but can be awkward for programming specific instances. in this paper we define a simple extension to the functional language haskell that makes these new notions of computation more convenient to use. our language is similar to the monadic style, and has similar reasoning properties. moreover, it is extensible, in the sense that new combining forms can be defined as expressions in the host language. ross paterson
generational reference counting: a reduced-communication distributed storage reclamation scheme  this paper describes generational reference counting, a new distributed storage reclamation scheme for loosely-coupled multiprocessors. it has a significantly lower communication overhead than distributed versions of conventional reference counting. although generational reference counting has greater computational and space requirements than ordinary reference counting, it may provide a significant saving in overall execution time on machines in which message passing is expensive.  the communication overhead for generational reference counting is one message for each copy of an interprocessor reference (pointer). unlike conventional reference counting, when a reference to an object is copied no message is sent to the processor on which the object lies. a message is sent only when a reference is discarded. unfortunately, generational reference counting shares conventional reference counting's inability to reclaim cyclical structures.  in this paper, we present the generational reference counting algorithm, prove it correct, and discuss some refinements that make it more efficient. we also compare it with weighted reference counting, another distributed reference counting scheme described in the literature.  b. goldberg
call forwarding: a simple interprocedural optimization technique for dynamically typed languages  this paper discusses call forwarding, a simple interprocedural optimization technique for dynamically typed languages. the basic idea behind the optimization is straightforward: find an ordering for the "entry actions" of a procedure, and generate multiple entry points for the procedure, so as to maximize the savings realized from different call sites bypassing different sets of entry actions. we show that the problem of computing optimal solutions to arbitrary call forwarding problems is np-complete, and describe an efficient greedy algorithm for the problem. experimental results indicate that (i) this algorithm is effective, in that the solutions produced are generally close to optimal; and (ii) the resulting optimization leads to significant performance improvements for a number of benchmarks tested.  koen de bosschere saumya debray david gudeman sampath kannan
pretenuring for java pretenuring can reduce copying costs in garbage collectors by allocating long-lived objects into regions that the garbage collector with rarely, if ever, collect. we extend previous work on pretenuring as follows. (1) we produce pretenuring advice that is neutral with respect to the garbage collector algorithm and configuration. we thus can and do combine advice from different applications. we find that predictions using object lifetimes at each allocation site in java prgroams are accurate, which simplifies the pretenuring implementation. (2) we gather and apply advice to applications and the jalapeño jvm, a compiler and run-time system for java written in java. our results demonstrate that building combined advice into jalapeño from different application executions improves performance regardless of the application jalapeño is compiling and executing. this _build-time_ advice thus gives user applications some benefits of pretenuring without any application profiling. no previous work pretenures in the run-time system. (3) we find that application-only advice also improves performance, but that the combination of build-time and application-specific advice is almost always noticeably better. (4) our same advice improves the performance of generational and older first colleciton, illustrating that it is _collector neutral_. stephen m. blackburn sharad singhai matthew hertz kathryn s. mckinely j. eliot b. moss
synchronous operations as first-class values  synchronous message passing via channels is an interprocess communication (ipc) mechanism found in several concurrent languages, such as csp, occam, and amber. such languages provide a powerful selective i/o operation, which plays a vital role in managing communication with multiple processes. because the channel ipc mechanism is "operation-oriented," only procedural abstraction techniques can be used in structuring the communication/synchronization aspects of a system. this has the unfortunate effect of restricting the use of selective i/o, which in turn limits the communication structure. we propose a new, "value- oriented" approach to channel-based synchronization. we make synchronous operations first-class values, called events, in much the same way that functions are first-class values in functional programming languages. our approach allows the use of data abstraction techniques for structuring ipc. we have incorporated events into pml, a concurrent functional programming language, and have implemented run-time support for them as part of the pegasus system.  j. h. reppy
an empirical evaluation of three methods for deadlock analysis of ada tasking programs  static analysis of ada tasking programs has been hindered by the well known state explosion problem that arises in the verification of concurrent systems. many different techniques have been proposed to combat this state explosion. all proposed methods excel on certain kinds of systems, but there is little empirical data comparing the performance of the methods. in this paper, we select one representative from each of three very different approaches to the state explosion problem: partial-orders (representing state- space reductions), symbolic model checking (representing obdd-based approaches), and inequality necessary conditions (representing integer programming-based approaches). we apply the methods to several scalable concurrency examples from the literature and to one real ada tasking program. the results of these experiments are presented and their significance is discussed.  james c. corbett
object-oriented parallel computation for plasma simulation  object- oriented techniques promise to improve the software design and programming process by providing an application-oriented view of programming while facilitating modification and reuse. since the software design crisis is particularly acute in parallel computation, these techniques have stirred the interest of the scientific parallel computing community. large-scale applications of ever-growing complexity, particularly in the physical sciences and engineering, require parallel processing for efficiency. since its introduction in the 1970s, fortran 77 has been the language of choice to model these problems, due to its efficiency, its numerical stability, and the body of existing fortran codes. however, the introduction of object-oriented languages provides new alternatives for parallel software development. fortran 90 adds modern extensions (including object-oriented concepts) to the established methods of fortran 77. alternatively, object-oriented methodologies can be explored through languages such as c++, eiffel, smalltalk, and many others. our selection among these required a language that was widespread and supported across multiple platforms (particularly supercomputers) with strong compiler optimizations. c++, while not a "pure" object-oriented language, was our choice, since it meets these criteria.  charles d. norton boleslaw k. szymanski viktor k. decyk