waashk/acm huggingface dataset:
distributed last call optimization for portable parallel logic programming  a difficult but challenging problem is the efficient exploitation of and and or parallelism in logic programs without making any assumptions about the underlying target machine(s). in earlier papers, we described the design of a binding environment for and and or parallel execution of logic programs on shared and nonshared memory machines and the performance of a compiler (called rolog) using this binding environment on a range of mimd parallel machines.  in this paper, we present an important optimization for portable parallel logic programming, namely  distributed last-call optimization, an analog of the tail recursion optimization for sequential prolog. this scheme has been implemented in the rolog compiler, which ports unchanged on several shared memory and nonshared memory machines. we describe the effect of this optimization on several or, and/or and and parallel benchmark programs.  balkrishna ramkumar
what's in a region?: or computing control dependence regions in near-linear time for reducible control flow  regions of control dependence identify the instructions in a program that execute under the same control conditions. they have a variety of applications in parallelizing and optimizing compilers. two vertices in a control-flow graph (which may represent instructions or basic blocks in a program) are in the same region if they have the same set of control dependence predecessors. the common algorithm for computing regions examines each control dependence at least once. as there may be o(v x e) control dependences in the worst case, where v and e are the number of vertices and edges in the control-flow graph, this algorithm has a worst-case running time of o(v x d). we present algorithms for finding regions in reducible control-flow graphs in near-linear time, without using control dependence. these algorithms are based on alternative definitions of regions, which are easier to reason with than the definitions based on control dependence.  thomas ball
a framework for visualizing object-oriented systems  this paper describes a new approach to visualizing program systems within the object- oriented paradigm. this approach is based on a tex-like notation which has been extended and generalized for specifying graphical layout of arbitrary objects. the clos meta-level architecture is used to associate visualization and application objects. we propose several useful techniques such as indirect values, slot and method demons, and instance-specific meta-objects. our techniques require no modifications to the systems which are selected for visualization. we demonstrate the feasibility of our approach using application domains such as clos debugging and constraint systems.  volker haarslev ralf möller
flattening and parallelizing irregular, recurrent loop nests  irregular loop nests in which the loop bounds are determined dynamically by indexed arrays are difficult to compile into expressive parallel constructs, such as segmented scans and reductions. in this paper, we describe a suite of transformations to automatically parallelize such irregular loop nests, even in the presence of recurrences. we describe a simple, general loop flattening transformation, along with new optimizations which make it a viable compiler transformation. a robust recurrence parallelization technique is coupled to the loop flattening transformation, allowing parallelization of segmented reductions, scans, and combining-sends over arbitrary associative operators. we discuss the implementation and performance results of the transformations in a parallelizing fortran 77 compiler for the cray c90 supercomputer. in particular, we focus on important sparse matrix-vector multiplication kernels, for one of which we are able to automatically derive an algorithm used by one of the fastest library routines available.  anwar m. ghuloum allan l. fisher
on the foundations of artificial workload design  the principles on which artificial workload model design is currently based are reviewed. design methods are found wanting for three main reasons: their resource orientation, with the selection of resources often unrelated to the performance impact of resource demands; their avoiding to define an accuracy criterion for the resulting workload model; and their ignoring the dynamics of the workload to be modeled. an attempt at establishing conceptual foundations for the design of interactive artificial workloads is described. the problems found in current design methods are taken into account, and sufficient conditions for the applicability of these methods are determined. the study also provides guidance for some of the decisions to be made in workload model design using one of the current methods.  domenico ferrari
guardians in a generation-based garbage collector  this paper describes a new language feature that allows dynamically allocated objects to be saved from deallocation by an automatic storage management system so that clean-up or other actions can be performed using the data stored within the objects. the program has full control over the timing of clean-up actions, which eliminates several potential problems and often eliminates the need for critical sections in code that interacts with clean-up actions. our implementation is "generation-friendly" in the sense that the additional overhead within a generation-based garbage collector is proportional to the work already done there, and the overhead within the mutator is proportional to the number of clean-up actions actually performed.  r. kent dybvig carl bruggeman david eby
reusing software developments  software development environments of the future will be characterized by extensive reuse of previous work. this paper addresses the issue of reusability in the context in which design is achieved by the transformational development of formal specifications into efficient implementations. it explores how an implementation of a modified specification can be realized by replaying the transformational derivation of the original and modifying it as required by changes made to the specification. our approach is to structure derivations using the notion of tactics, and record derivation histories as an execution trace of the application of tactics. one key idea is that tactics are compositional: higher level tactics are constructed from more rudimentary using defined control primitives. this is similar to the approach used in lcf[12] and nuprl[1, 8].  given such a derivation history and a modified specification, the correspondence problem [21, 20] addresses how during replay a correspondence between program parts of the original and modified program is established.  our approach uses a combination of name association, structural properties, and associating components to one another by intensional descriptions of objects defined in the transformations themselves.  an implementation of a rudimentary replay mechanism for our interactive development system is described. for example with the system we can first derive a program from a specification that computes some basic statistics such as mean, variance, frequency data, etc. the derivation is about 15 steps; it involves deriving an efficient means of computing frequency data, combining loops and selecting data structures. we can then modify the specification by adding the ability to compute the maximum or mode and replay the steps of the previous derivation.  allen goldberg
experiments with typing in process modeling  much of our recent work has been predicated on the hypothesis that extensive use of typing will be an important aspect of creating and using process models. in particular, we have been actively investigating type models specifically tailored for use in software environment and process model definition. we recently used class projects in two different software engineering courses as preliminary experiments on the efficacy of typing in creating process models. in this paper we sketch our type model work, describe the experiments and offer a brief assessment of the results.  jack c. wileden
checkpoint - restart for apl applications  the crash proofing of apl programs is relatively simple in an apl system having a file sub-system. the method is the classical check point and restart to which has been added completion codes. it can be used for single user programs or multiple user interactive programs with critical sections. it assures recovery for such external generated failures as cpu, terminal, telephone line drop, or network crashes. the method can be used on already written programs by simple insertion in the existent code. it is particularly useful in application programs where the users are laymen.  otway o. pardee
transportable applications environment (tae) plus experiences in "object"-ively modernizing a user interface environment  this paper describes the evolution of the transportable applications executive (tae) (developed at nasa/goddard space flight center) from a traditional procedural menu and command-oriented system to an object-oriented, modeless user interface management system, known as tae plus. the impetus for developing this environment and early experiments which led to its current implementation are addressed. the current version of tae plus provides design and prototyping functions, working in tandem with a mature application management system. the main components are (1) a user interface designers' workbench that allows an application developer to interactively layout an application screen and define the static and/or dynamic areas of the screen; (2) an application programmer subroutine package that provides runtime services used to display and control workbench-designed "interaction objects" on the screen; and (3) an extension to the existing tae command language that provides commands for displaying and manipulating interaction objects, thus providing a means to quickly prototype an application's user interface. during tae plus development, many design and implementation decisions were based on the state- of-the-art within graphics workstations, windowing systems and object-oriented programming languages, and this paper shares some of the problems and issues experienced during implementation. some of the topics discussed include: lessons learned in using the smalltalk language to prototype the initial workbench; why c++ was selected (over other languages) to build the workbench; and experiences in using x window system and stanford's interviews object library. the paper concludes with open issues and a description of the next steps involved in implementing the "totally modern" tae.  martha r. szczur philip miller
dynamo: a transparent dynamic optimization system  we describe the design and implementation of dynamo, a software dynamic optimization system that is capable of transparently improving the performance of a native instruction stream as it executes on the processor. the input native instruction stream to dynamo can be dynamically generated (by a jit for example), or it can come from the execution of a statically compiled native binary. this paper evaluates the dynamo system in the latter, more challenging situation, in order to emphasize the limits, rather than the potential, of the system. our experiments demonstrate that even statically optimized native binaries can be accelerated dynamo, and often by a significant degree. for example, the average performance of -o optimized specint95 benchmark binaries created by the hp product c compiler is improved to a level comparable to their -o4 optimized version running without dynamo. dynamo achieves this by focusing its efforts on optimization opportunities that tend to manifest only at runtime, and hence opportunities that might be difficult for a static compiler to exploit. dynamo's operation is transparent in the sense that it does not depend on any user annotations or binary instrumentation, and does not require multiple runs, or any special compiler, operating system or hardware support. the dynamo prototype presented here is a realistic implementation running on an hp pa-8000 workstation under the hpux 10.20 operating system.  vasanth bala evelyn duesterwald sanjeev banerjia
an interactive debugging tool for c based on dynamic slicing and dicing  static program slicing has gained wide recognition in both academic and practical arenas. several debugging tools have been developed that utilize static program slicing. dynamic slicing has also gained considerable popularity in recent years. due to the several advantages of dynamic slicing over static slicing, the objective of this work was to develop a debugging tool for c programs, called c-debug, using dynamic slicing and dicing techniques. this paper reports the design considerations of c-debug and the data structures used in the implementation of c-debug. based on the usage experiments with the c-debug debugging tool, limitations and possible future enhancements are also outlined.  m. samadzadeh w. wichaipanitch
towards monolingual programming environments  most programming environments are much too complex. one way of simplifying them is to reduce the number of mode-dependent languages the user has to be familiar with. as a first step towards this end, the feasibility of unified command/programming/debugging languages, and the concepts on which such languages have to be based, are investigated. the unification process is accomplished in two phases. first, a unified command/programming framework is defined and, second, this framework is extended by adding an integrated debugging capability to it. strict rules are laid down by which to judge language concepts presenting themselves as candidates for inclusion in the framework during each phase. on the basis of these rules many of the language design questions that have hitherto been resolved this way or that, depending on the taste of the designer, lose their vagueness and can be decided in an unambiguous manner.  jan heering paul klint
sharlit - a tool for building optimizers  a complex and time-consuming function of a modern compiler is global optimization. unlike other functions of a compiler such as parsing and code generation which examine only one statement or one basic block at a time, optimizers are much larger in scope, examining and changing large portions of a program all at once. the larger scope means optimizers must perform many program transformations. each of these transformations makes its own particular demands on the internal representation of programs; each can interact with and depend on the others in different ways. this makes optimizers large and complex.  despite their complexity, few tools exist to help in building optimizers. this is in stark contrast with other parts of the compiler where years of experience have culminated in tools with which these other parts can be constructed easily. for example, parser generators are used to build front- ends, and peephole optimizers and tree matchers are used to build code generators.  this paper presents sharlit, a tool to support the construction of modular and extensible global optimizers. we will show how sharlit helps in constructing data-flow analyzers and the transformations that use data-flow analysis information, both are major components of any optimizer.  sharlit is implemented in c++ and uses c++ in the same way that yacc uses c. thus we assume the reader has some familiarity with c++[9].  steven w. k. tjiang john l. hennessy
points-to analysis for java using annotated constraints the goal of point-to analysis for java is to determine the set of objects pointed by a reference variable or a reference object field. this information has a wide variety of client applications in optimizing compilers and software engineering tools. in this paper we present a point-to analysis for java based on andersen's point- to analysis for c [5]. we implement the analysis by using a constraint-based approach which employs _annotated inclusion constraints._ constraint annotations allow us model precisely and efficiently the semantics of virtual calls and the flow of values through object fields. by solving systems of annotated inclusion constraints, we have been albe to perform practical and precies points-to analysis for java atanas rountev ana milanova barbara g. ryder
on statecharts with overlapping  the problem of extending the language of statecharts to include overlapping states is considered. the need for such an extension is motivated and the subtlety of the problem is illustrated by exhibiting the shortcomings of naive approaches. the syntax and formal semantics of our extension are then presented, showing in the process that the definitions for conventional statecharts constitute a special case. our definitions are rather complex, a fact that we feel points to the inherent difficulty of such an extension. we thus prefer to leave open the question of whether or not it should be adopted in practice.  david harel chaim- arie kahana
models for visualization in parallel debuggers  the complexity of parallel programming has stimulated the development of a variety of debugging tools. this survey of recent research focuses on debugger visualization systems. the effectiveness of such systems is bounded by the degree to which their representations of run-time behavior correlate with the language structures used to incorporate parallelism, as well as the logical framework adopted by the programmer. current visualization systems are compared with the conceptual models supported by parallel languages. attention is drawn to the fact that debuggers are tied to specific models and that this association may restrict their usefulness and acceptability.  c. m. pancake s. utter
an object-oriented apl2  object oriented programming has become an important and accepted part of the computer software industry. nearly every new operating system that has recently arrived or is scheduled to arrive soon is object oriented in nature. if apl2 is to continue to be a mainstream computational environment, it is very important that it becomes object oriented.  finding a way that apl2 may sit comfortably in these new operating systems is important. unfortunately, in both implementation and current programming teaching philosophy, existing apl2 does not easily offer the end user the ability to adopt this new approach. this paper proposes some small changes to the basic apl2 language definition which will permit objects to be defined and used. it also suggests some major changes to the end user's programming methodology.  david a. selby
distributed software prototyping with ads  the difficulties ordinarily experienced in designing and developing large software systems are greatly increased in the case of distributed data processing (ddp) systems. thus there is an urgent need to support the software life cycle activities with effective prototyping tools and techniques. the architecture development system (ads) is being developed for use in prototyping ddp systems within a distributed testbed. ads features an interactive graphical user interface, a distributed runtime environment, and a prototyping framework based on the concept of abstract ddp objects with attributes and relationships. this paper presents the ads prototyping features and the user interface to describe, synthesize, execute and analyze system representations. then a discussion is presented of the applicability of ads support to the distributed software life cycle. the current implementation status of ads is also summarized.  james w. hooper john t. ellis tony a. johnson
systemc: a homogenous environment to test embedded systems  _the systemc language is becoming a new standard in the eda field and many designers are starting to use it to model complex systems. systemc has been mainly adopted to define abstract models of hardware/software components, since they can be easily integrated for rapid prototyping. however, it can also be used to describe modules at a higher level of detail, e.g., rt-level hardware descriptions and assembly software modules. thus, it would be possible to imagine a systemc-based design flow, where the system description is translated from one abstraction level to the following one by always using systemc representations. the adoption of a systemc-based design flow would be particularly efficient for testing purpose as shown in this paper. in fact, it allows the definition of a homogeneous testing procedure, applicable to all design phases, based on the same error model and on the same test generation strategy. moreover, test patterns are indifferently applied to hardware and software components, thus making the proposed testing methodology particularly suitable for embedded systems. test patterns are generated on the systemc description modeling the system at one abstraction level, then, they are used to validate the translation of the system to a lower abstraction level. new test patterns are then generated for the lower abstraction level to improve the quality of the test set and this process is iterated for each translation (synthesis) step._  alessandro fin franco fummi maurizio martignano mirko signoretto
a critique of common lisp  a major goal of the common lisp committee was to define a lisp language with sufficient power and generality that people would be happy to stay within its confines and thus write inherently transportable code. we argue that the resulting language definition is too large for many short-term and medium-term potential applications. in addition many parts of common lisp cannot be implemented very efficiently on stock hardware. we further argue that the very generality of the design with its different efficiency profiles on different architectures works against the goal of transportability.  rodney a. brooks richard p. gabriel
software engineering session overview and introductory comments  for the fourth consecutive year, the national acm conference is giving attention to the field of software engineering. this year builds on what has gone before---"structured program planning and design: standardization needs" (acm '79 - detroit), "more on structured design" (acm '80 - nashville), and the "software engineering tutorial" (acm '81 - los angeles)---providing for some measure of continuity. this session contains original papers stressing techniques for implementing reliable, maintainable, well-engineered software. presented are state-of-the-art applications of software engineering techniques addressing architectural, structural, behavioral, and informational considerations.  the ariel pashtan paper "object oriented operating systems: an emerging design methodology" emphasizes architectural considerations. this survey analyzes eight major operating systems. these operating systems undergo a functional decomposition with a view toward the behavioral and informational requirements by way of the object model concept. pashtan shows us how object implementation techniques may be applied and leaves us to consider "whether 'thinking in terms of objects' will become a standard design methology for operating systems".  murray r. berkowitz
towards effective embedded processors in codesigns: customizable partitioned caches  _this paper explores an application-specific customization technique for the data cache, one of the foremost area/power consuming and performance determining microarchitectural features of modern embedded processors. the automated methodology for customizing the processor microarchitecture that we propose results in increased performance, reduced power consumption and improved determinism of critical system parts while the fixed design ensures processor standardization. the resulting improvements help to enlarge the significant role of embedded processors in modern hardware/software codesign techniques by leading to increased processor utilization and reduced hardware cost. a novel methodology for static analysis and a field-reprogrammable implementation of a customizable cache controller that implements a partitioned cache structure is proposed. the simulation results show significant decrease of miss ratio compared to traditional cache organizations._  peter petrov alex orailglu