bluuebunny/crossref_metadata_2025 huggingface dataset:
The elaboration order problem of ada
Authors: Lander Leslie C. , Mitra Sandeep , Singhvi Nitin , Piatkowski Thomas F.
Published: November 2006

A serious problem in large Ada programs is finding a satisfactory order of elaboration for all of the program's compilation units. Some elaboration sequence must be selected but access to a program entity before its elaboration will raise the exception (PROGRAM_ERROR) shortly after execution of the program begins. The rules of the 1983 Ada standard1fail to ensure that validated compilers produce a satisfactory elaboration order, or report an error if static analysis shows that such an order may not exist. The problem can make programs non‐portable and sensitive to modifications. This paper presents an algorithm ada_elab which determines an order of elaboration, free of PROGRAM_ERROR, if link‐time, static analysis can determine that there is one. Examples are used to illustrate the occurrence of elaboration errors and the inadequacy of pragma ELABORATE to resolve the problem. The paper closes with descriptions of elaboration and elaboration‐related problems that cannot be handled by ada_elab, access before initialization and coding practices that should avoid elaboration and initialization errors. While Ada is the subject of this paper, the problem being studied could occur in any language that permits a complex initialization of individual program modules prior to the execution of the main program module.
The evolution of an object‐oriented compiler framework
Authors: Graver Justin O.
Published: November 2006

Increasing code reuse in software systems is an important way to decrease development and maintenance costs, reduce the time required to respond to new requirements, and significantly advance the feasible complexity limits for new systems. Object‐oriented programming languages and environments provide fundamental support for truly reusable code through abstraction, inheritance, and polymorphism. Reusable code is a prerequisite for a significantly more powerful concept: reusable design. Frameworks of resuable design abstractions are difficult to create and typically evolve over a long period of use and refinement. Thus, it is important to understand how systems evolve and how this evolution can be directed to achieve the best results.

This article illustrates some of the standard transformations, called refactorings, that occur in object‐oriented systems as they evolve by describing the creation and evolution of a framework for building general‐purpose string‐to‐object translators. It reflects our experiences with object‐oriented compilers over a five year period while working on the Typed Smalltalk compiler project.
Practical experience with OS/2 installable file systems
Authors: Ogle David M. , Sullivan Neil G. , Williams E. Hollins
Published: November 2006

The installable file system (IFS) faculty on OS/2 offers an efficient mechanism for expanding the abilities of the OS/2 kernel. Two prototypes illustrate the usefulness of the IFS facility. An OS/2 port of the Andrew File System (AFS) allows users to access global community files while retaining the private local file system on the OS/2 machine. An IFS implementation of a network protocol mapper, which maps TCP/IP socket calls to SNA Advanced Program‐to‐Program Communication (APPC) calls, provides the ability to run any socket program on an APPC network after simply re‐linking with the mapping library. The only impediment to the development of these prototypes is the lack of kernel‐level interfaces to operating system devices, resulting in time‐consuming data movement back up to the user level to access the network and the local disks. This impediment will disappear as OS/2 and its associated support software matures.
Issues in porting software from c to c++
Authors: Hashemi Reza , Leach Ronald J.
Published: November 2006

This paper describes an experiment in the development of a small piece of software in both the languages C and C++ in a university setting. The C++ codes were found to be more modular than the corresponding C codes. Some of the other effects of C++ on program quality are very briefly discussed.

The paper also discusses some of the errors that C programmers may make as novice C++ programmers, and the testing of object‐oriented programs. Some of the error types possible in C++, but not in C, include delays in the flushing of output buffers and polymorphism.
A group process for defining local software quality: Field applications and validation experiments
Authors: Trammell Carmen J. , Poore J. H.
Published: November 2006

‘Global’ measures of software quality are generally not used by practitioners because they have not been calibrated for local operating environments. A participative process for defining local software quality has been defined, applied in the field, and evaluated in formal validation experiments. In four field applications of the process, a ‘jury’ of seasoned practitioners ranked a sample of modules from the organization's inventory of code and produced a ‘software quality rule set’. The results of each field application were tested in a formal validation experiment to determine whether the obtained rule set was a valid representation of the organization's sense of quality, i.e. whether the locally‐derived rules could enable non‐organizational programmers to make judgments about quality that were similar to those of the jury. In each experiment, non‐organizational programmers ranked the same set of modules that were ranked by the organization's jury, using either the locally‐derived rules, generic (textbook) rules, placebo (non‐helpful) rules, or no rules. The correlation between the judgments of non‐organizational programmers using local rules and the jury was statistically significant at p < 0–005; all other correlations were significant at p < 0–005. The results support a conclusion that the group process for defining local software quality is reliable in producing valid rule sets.
Garbage collection alternatives for icon
Authors: Fernandez Mary F. , Hanson David R.
Published: November 2006

Copying garbage collectors are becoming the collectors of choice for very high‐level languages and for functional and object‐oriented languages. Copying collectors are particularly efficient for large storage regions because their execution time is proportional only to the amount of accessible data, and they identify and compact this data in one pass. In contrast, mark‐and‐sweep collectors execute in time proportional to the memory size and compacting collectors require another pass to compact accessible data. The performance of existing systems with old compacting mark‐and‐sweep collectors might be improved by replacing their collectors with copying collectors. This paper explores this possibility by describing the results of replacing the compacting mark‐and‐sweep collector in the Icon programming language with four alternative collectors, three of which are copying collectors. Copying collectors do indeed run faster than the original collector, but at a significant cost in space. An improved variant of the compacting mark‐and‐sweep collector ran even faster and used little additional space.
Exceptional C or C with exceptions
Authors: Gehani N. H.
Published: November 2006

C does not have exception handling facilities. Errors are handled by examining the value returned by each function and signals (conditions reported to the program) are handled by using library functions. These approaches lead to ad hoc error‐handling techniques and can make programs hard to understand. Exceptional C, a superset of C, provides exception handling facilities. Exceptional C integrates the two techniques used by C programmers (i.e., status values and signals) to handle errors into one unified exception handling mechanism. In this paper, I review exception handling models, specify the criteria used for designing the exception handling facilities in Exceptional C, and then describe these facilities. I also illustrate the use of the exception handling facilities with examples.
Linkage analysis of processes
Authors: Yaung Alan T. , Raz Tzvi
Published: November 2006

This paper presents a methodology for the analysis of the linkage among the processes in an organization. The methodology has three main steps: model construction; connectivity analysis; and structure analysis. The model construction step generates a linkage matrix which is used in the following steps. The connectivity analysis is based on linkage consistency and interprocess coupling metrics, which are defined for each process individually and for all the processes in the organization as a group. The clustering algorithm is based on a linkage intensity measure derived from the linkage matrix. Following a detailed description of the methodology and its metrics and algorithms, the results obtained in a medium‐size software development organization are presented.
Stress testing of compilers for modula‐2
Authors: Pronk C.
Published: November 2006

During standardization discussions on Modula‐2 the question was raised whether the future standard should need a clause stating a set of minimal requirements for conforming implementations regarding the ‘structuredness’ of lexical, syntactical and run‐time constructs in programs written in this language. It was decided to test a number of compilers to find their actual limits on the structuredness of some of these constructs. The test results do not only show these limits, but the inability of some compilers to handle large and complex inputs is shown as well.
Experimenting with dynamic linking with ADA
Authors: Inverardi Paola , Mazzanti Franco
Published: November 2006

An approach to achieving dynamic reconfiguration within the framework of Ada1 is described. A technique for introducing a kernel facility for dynamic reconfiguration in Ada is illustrated, and its implementation using the Verdix VADS 5.5 Ada compiling system on a Sun3–120 running the 4.3 BSD Unix operating system is discussed. This experimental kernel allows an Ada program to change its own configuration dynamically, linking new pieces of code at run‐time. It is shown how this dynamic facility can be integrated consistently at the Ada language level, without introducing severe inconsistencies with respect to the Standard semantics.
Applications of finite automata representing large vocabularies
Authors: Lucchesi Cláudio L. , Kowaltowski Tomasz
Published: November 2006

The construction of minimal acyclic deterministic partial finite automata to represent large natural language vocabularies is described. Applications of such automata include spelling checkers and advisers, multilanguage dictionaries, thesauri, minimal perfect hashing and text compression.
Techniques for fast instruction cache performance evaluation
Authors: Whalley David B.
Published: November 2006

Cache performance has become a very crucial factor in the overall system performance of machines. Effective analysis of a cache design requires the evaluation of the performance of the cache for typical programs that are to be executed on the machine. Recent attempts to reduce the time required for such evaluations either result in a loss of accuracy or require an initial pass by a filter to reduce the length of the trace. This paper evaluates techniques that attempt to overcome these problems for instruction cache performance evaluation. For each technique variations with and without periodic context switches are examined. Information calculated during the compilation is used to reduce the number of references in the trace. Thus, in effect references are stripped before the initial trace is generated. These techniques are shown to significantly reduce the time required for evaluating instruction caches with no loss of accuracy.
Experience with PMS‐Prolog: A distributed, coarse‐grain‐parallel prolog with processes, modules and streams
Authors: Wise Michael J.
Published: November 2006

PMS‐Prolog is an implementation of Prolog designed for distributed systems, and therefore uses coarsegrain parallelism in preference to the fine‐grain parallelism of other implementations. Prolog processes are formally defined and interprocess communication is explicit. An overview of PMS‐Prolog is provided, followed by an examination of the PMS‐Prolog solutions to four problems. These solutions are also compared to other solutions from the literature. From this, the strengths and weaknesses of the PMS‐Prolog model can be seen. Avenues for improving the model are then suggested.
Reducing object storage requirements in a multi‐user environment
Authors: Boysen Pete , Shah Pinaki
Published: November 2006

Many Smalltalk implementations store objects in a large file called a virtual image. Each user must have a copy of the virtual image to execute. Since the image can exceed a megabyte in size, considerable disk space is required to support such a system in a multi‐user environment. In this paper, a method is described which can reduce storage requirements for systems which use generation scavenging as a memory reclamation technique. This method also improves the performance of the checkpoint operation and offline garbage‐collection.
Success rate of interpolation in subsegment prediction
Authors: Wright William E. , Jeyaratnam Sakthivel
Published: November 2006

We consider the accuracy of linear interpolation in predicting which subsegment contains a random key, given that the key is contained in a particular segment consisting of a fixed number of subsegments. We assume that keys are stored in a file in sorted order, that the file is divided into fixed‐size segments, and that the first key in the segment containing the desired key is known, as is the first key of the next segment. We present empirical results for real files in which keys are social security numbers, names and telephone numbers, and for files of keys generated randomly from the uniform and from the exponential distributions. We present a theoretical analysis of the average success rate for the case in which keys are uniformly distributed. We show that the success rate depends on the number of subsegments in a segment, the size of a subsegment, and the distribution of keys, and that it is much higher than for random guessing. We describe practical applications in which this technique can be efficiently used.
Bonsai: A compact representation of trees
Authors: Darragh John J. , Cleary John G. , Witten Ian H.
Published: November 2006

This paper shows how trees can be stored in a very compact form, called ‘Bonsai’, using hash tables. A method is described that is suitable for large trees that grow monotonically within a predefined maximum size limit. Using it, pointers in any tree can be represented within 6 + [log2n] bits per node where n is the maximum number of children a node can have. We first describe a general way of storing trees in hash tables, and then introduce the idea of compact hashing which underlies the Bonsai structure. These two techniques are combined to give a compact representation of trees, and a practical methodology is set out to permit the design of these structures. The new representation is compared with two conventional tree implementations in terms of the storage required per node. Examples of programs that must store large trees within a strict maximum size include those that operate on trie structures derived from natural language text. We describe how the Bonsai technique has been applied to the trees that arise in text compression and adaptive prediction, and include a discussion of the design parameters that work well in practice.
Visualizing a hierarchy of performance models for software systems
Authors: Ammar Reda A. , Rosiene Carolyn Pe
Published: November 2006

Definition of a software process to be analyzed is normally top‐down. Analysis starts with a rough description and evolves into finer granularity as more performance and functional requirements become available. This process involves different performance models at each stage. The relationship between these models forms a hierarchy of performance models. Performance parameters propagate bottom‐up and the analysis of these models is very complex, so that it is essential to develop computer aided performance evaluation (CAPE) tools to support the evaluation process. In this work, we developed a graphical interface for CAPE environments called the GRAphical Performance Evaluation (GRAPE) system. GRAPE supports the structural design of five different performance models: queueing, state, computation structure, data flow and statistical models. These models can be used to design parallel/distributed real‐time software systems at different levels of granularity. GRAPE is the front‐end tool for a CAPE environment that will allow the user to integrate the relationships between different performance metrics at different levels of analysis. These metrics propagate between the modeling hierarchy to arrive at a final quantitative or symbolic measure of its performance.
Kibitz—connecting multiple interactive programs together
Authors: Libes Don
Published: November 2006

Expect is a programming language for automating interactive programs. Recently, people have begun using Expect to connect multiple interactive programs together, allowing for new classes of applications. With some basic building blocks and a little scripting, it is possible to build such applications quickly.

This paper discusses the general technique, while focusing on a particular example: Kibitz. Kibitz connects multiple sessions and applications together, providing a means for consulting, group editing, or other cooperative tasks. Kibitz in turn, can be used as a module in building additional programs of this type. Using Kibitz, we demonstrate how to enable cron or background processes to call upon and interact with users, e.g. for guidance or debugging.

Owing to program reuse, our approach avoids many portability issues already addressed and solved by existing programs. Kibitz has no special coding for byte swapping, structure encoding, or job control, and requires neither kernel modifications nor setuid or other permissions even though it runs over a network and deals with multiple users, job control, and sophisticated programs such as shells and fullscreen editors.
Reducing compilation time by a compilation server
Authors: Onodera Tamiya
Published: November 2006

In language systems that support separate compilation, we often observe that header files are internalized over and over again when the source files that depend on them are compiled. Making a compiler a long‐lived server eliminates such redundant processing of header files, thus reducing the compilation time. The paper first describes compilation servers for C‐family languages in general, and then a compilation server for our C‐based object‐oriented language in particular. The performance results of our server show that a compilation server can substantially shorten the compilation time.
An execution profiler for window‐oriented applications
Authors: Gupta Aloke , Hwu Wen‐Mei W.
Published: November 2006

Execution profiles are important in analyzing the performance of computer programs on a given computer system. However, accurate and complete profiles are difficult to arrive at for programs that follow the client‐server model of computing, as in the popular X Window System. In X Window applications, considerable computation is invoked at the display server and this computation is an important part of the overall execution profile. The profiler presented in this paper generates meaningful profiles for X Window applications by estimating the time spent in servicing the messages in the display server. The central idea is to analyze a protocol‐level trace of the interaction between the application and the display server and thereby construct an execution profile from the trace and a set of metrics about the target display server. Experience using the profiler for examining bottlenecks is presented.
Lexical analysis of inflected Arabic words using exhaustive search of an augmented transition network
Authors: Rafea Ahmed A. , Shaalan Khaled F.
Published: November 2006

This paper presents a lexical analyser for inflected Arabic words. An augmented transition network (ATN) technique was used to represent the context‐sensitive knowledge about the relation between a stem and inflectional additions. An exhaustive‐search algorithm is developed to traverse the ATN, generating all possible interpretations of an inflected Arabic word. The arcs of the ATN are augmented with rules containing conditions and actions. More than one rule is associated with some arcs. The states of the ATN are represented by Pascal procedures.
Debugging with dynamic slicing and backtracking
Authors: Agrawal Hiralal , Demillo Richard A. , Spafford Eugene H.
Published: November 2006

Programmers spend considerable time debugging code. Symbolic debuggers provide some help but the task remains complex and difficult. Other than breakpoints and tracing, these tools provide little high‐level help. Programmers must perform many tasks manually that the tools could perform automatically, such as finding which statements in the program affect the value of an output variable for a given test case, and what was the value of a given variable when the control last reached a given program location. If debugging tools provided explicit support for these tasks, the debugging process could be automated to a significant extent.

In this paper we present a debugging model, based on dynamic program slicing and execution backtracking techniques, that easily lends itself to automation. This model is based on experience with using these techniques to debug software. We also present a prototype debugging tool, SPYDER, that explicitly supports the proposed model, and with which we are performing further debugging research.
Emulating an operating system on top of another
Authors: Franz Michael
Published: November 2006

In this paper, we present the design of an operating‐system emulator. This software interface provides the services of one operating system (Oberon) on a machine running a different operating system (Macintosh), by mapping the functions of the first onto equivalent calls to the second. The construction of this emulator proceeded in four distinct phases, documented here through examples from each of these phases. We believe that our four‐phase approach can be beneficial whenever a larger software system needs to be adapted from one architecture onto another. In conclusion, we relate some of the lessons learned and propose guidelines for similar engineering projects.
Lock‐and‐key strategies for handling undefined variables
Authors: Borie Richard B. , Parrish Allen S. , Mandyam Srinivas
Published: November 2006

Most programming languages ignore the problem of undefined variables and permit compilers to allow the leftover contents of the memory cells belonging to such variables to be referenced. Although efficient, this type of semantics does not support software engineering, because defects might arise in subtle ways and might be difficult to locate. Two other types of semantics that better support software engineering are to either initialize all variables to some default, e.g. zero, or to require that all references to undefined variables be treated as errors. However, these types of semantics are obviously more expensive than simply ignoring the undefined variables entirely.

In this paper, we propose a simple technique that works equally well for both of these latter two types of semantics, and whose efficiency compares favorably for certain realistic programs with more traditional implementations of these semantics. Furthermore, we provide a mechanism for using this technique through Ada implementations of two abstract data types where undefined variables respectively exhibit these two types of semantics, and whose implementations of these semantics use our technique. These abstract data types allow our technique to be selectively used in strictly those situations where the cost of the technique is justified. We provide practical examples illustrating these situations.
Longest‐match string searching for ziv‐lempel compression
Authors: Bell Timothy , Kulp David
Published: November 2006

Ziv‐Lempel coding is currently one of the more practical data compression schemes. It operates by replacing a substring of a text with a pointer to its longest previous occurrence in the input, for each coding step. Decoding a compressed file is very fast, but encoding involves searching at each coding step to find the longest match for the next few characters. This paper presents eight data structures that can be used to accelerate the searching, including adaptations of four methods normally used for exact matching searching. The algorithms are evaluated analytically and empirically, indicating the trade‐offs available between compression speed and memory consumption. Two of the algorithms are well‐known methods of finding the longest match—the time‐consuming linear search, and the storage‐intensive trie (digital search tree). The trie is adapted along the lines of a PATRICIA tree to operate economically. Hashing, binary search trees, splay trees and the Boyer‐Moore searching algorithm are traditionally used to search for exact matches, but we show how these can be adapted to find longest matches. In addition, two data structures specifically designed for the application are presented.
Aesthetic layout of generalized trees
Authors: Bloesch Anthony
Published: November 2006

Research on the aesthetic layout of trees has been largely concerned with the special case of binary trees with small constant‐sized nodes. Yet, without otherwise requiring the power of general graph‐layout algorithms, many layout problems involve n‐ary trees with variable‐sized nodes. This paper addresses the general issue of the aesthetic layout of such trees. Two algorithms are presented for the layout of generalized trees, and general issues, such as appropriate aesthetics, are discussed. The algorithms described are suitable for such tasks as the layout of class hierarchies, directory trees and tableau‐style proofs.
Pictures that play: Design notations for real‐time and distributed systems
Authors: Buhr R. J. A.
Published: November 2006

‘Pictures that play’ are design diagrams that give enough visual cues to enable a person to trace causality sequences that cut across them, without referring to (or even knowing) the kind of details that would enable a tool to execute the design or to generate executable code. Playing design diagrams is particularly important while exploring alternative solutions during the early stages of designing all kinds of systems. It is done either by mentally tracing sequences across diagrams on paper or a computer screen, or physically tracing them on whiteboards with a pointer or finger during design meetings. Two complementary pictorial design notations are described and used together in an example to illustrate the concept of play and to show how to do it: timethreads, a new notation for causality sequences that cut across many components and across the system end‐to‐end, and machine charts, an older notation for architecture presented here from a new angle. These notations are specifically designed to support play during the design process, not just record the end result. The focus is on real‐time and distributed (RTD) systems, but the approach has wider applicability.
Compile‐time copy elimination
Authors: Schnorf Peter , Ganapathi Mahadevan , Hennessy John L.
Published: November 2006

Single‐assignment and functional languages have value semantics that do not permit side‐effects. This lack of side‐effects makes automatic detection of parallelism and optimization for data locality in programs much easier. However, the same property poses a challenge in implementing these languages efficiently. This paper describes an optimizing compiler system that solves the key problem of aggregate copy elimination. The methods developed rely exclusively on compile‐time algorithms, including interprocedural analysis, that are applied to an intermediate data flow representation. By dividing the problem into update‐in‐place and build‐in‐place analysis, a small set of relatively simple techniques—edge substitution, graph pattern matching, substructure sharing and substructure targeting—was found to be very powerful. If combined properly and implemented carefully, the algorithms eliminate unnecessary copy operations to a very high degree. No run‐time overhead is imposed on the compiled programs.
Interprocedural alias analysis: Implementation and empirical results
Authors: Mayer Herbert G. , Wolfe Michael
Published: November 2006

We report our experiences with the implementation of InterProcedural Alias Analysis (IPA) for Fortran. Implicit aliasing caused by reference parameter passing can be uncovered in a program with multiple compilation units by interprocedural analysis. For scalar objects and for full arrays, the IPA processor described here finds all alias relations. For indexed array elements and partial arrays, conservative assumptions must still be made in the absence of precise knowledge about the subscripts. IPA has been integrated into nascent, the front‐end of a Fortran translator under development at the Oregon Graduate Institute (OGI). This report explains the goals and limitations of alias analysis for conventional procedural languages with reference parameters, shows in detail the actual design and implementation of IPA, and provides algorithmic and speed improvements over the best previously known aliasing algorithms. Empirical results gathered during the analysis of large Fortran programs are also listed and discussed.
Supra‐RPC: Subprogram parameters in remote procedure calls
Authors: Stoyenko Alexander D.
Published: November 2006

Remote‐procedure calls (RPCs) allow distributed, high‐level language programs to communicate and synchronize in the usual manner via subprogram calls. One of the great challenges in RPC research is to preserve the traditiional call semantics despite the distribution and heterogeneity of the new environment.

The main contribution of SUPRA‐RPC is in addressing the passing of subprograms as RPC parameters. In doing so, SUPRA overcomes a number of technical difficulties, stemming from scoping, side‐effects and other sources. Since supporting subprogram RPC parameters is harder than supporting non‐subprogram RPC parameters, the three (of six) components of the SUPRA architecture extend in novel ways the traditional functionality found in their counterparts in other RPC systems. The SUPRA stub generator extracts information not only from remote entry interfaces, but from any scope potentially referenced by a subprogram passed as an RPC parameter. In addition to the usual call‐ and accept‐stubs and the marshaling and unmarshaling routines, the generator constructs out‐of‐scope access stubs, callback' and callback‐handling‐stubs, and modified parameter subprograms and others. The SUPRA run‐time support manages a run‐time symbol table to keep track of referencing environments and out‐of‐scope objects. When an out‐of‐scope object is unavailable for access or execution on the server, the object is reached by a synchronous, ‘under‐the‐covers’ callback. The SUPRA process management supports servers with independent threads of control, manages (possibly nested) callbacks and pools of callback handler threads, and maintains correct identification of thread‐initiated calls or callbacks.

A SUPRA prototype has been implemented on Sun Unix workstations. The prototype supports C, C++ and CommonLisp programs. A prototype graphical demonstration has been implemented as well, that represents RPC concepts in terms of common life objects and situations.
Compilation of functional languages using flow graph analysis
Authors: Hartel Pieter H. , Glaser Hugh , Wild John M.
Published: November 2006

A system based on the notion of a flow graph is used to specify formally and to implement a compiler for a lazy functional language. The compiler takes a simple functional language as input and generates C. The generated C program can then be compiled, and loaded with an extensive run‐time system to provide the facility to experiment with different analysis techniques. The compiler provides a single, unified, efficient, formal framework for all the analysis and synthesis phases, including the generation of C. Many of the standard techniques, such as strictness and boxing analyses, have been included.
Rewriting executable files to measure program behavior
Authors: Larus James R. , Ball Thomas
Published: November 2006

Inserting instrumentation code in a program is an effective technique for detecting, recording, and measuring many aspects of a program's performance. Instrumentation code can be added at any stage of the compilation process by specially‐modified system tools such as a compiler or linker or by new tools from a measurement system. For several reasons, adding instrumentation code after the compilation process—by rewriting the executable file—presents fewer complications and leads to more complete measurements.

This paper describes the difficulties in adding code to executable files that arose in developing the profiling and tracing tools qp and qpt. The techniques used by these tools to instrument programs on MIPS and SPARC processors are applicable in other instrumentation systems running on many processors and operating systems. In addition, many difficulties could have been avoided with minor changes to compilers and executable file formats. These changes would simplify this approach to measuring program performance and make it more generally useful.
The design and implementation of genesis
Authors: Whitfield Deborah , Soffa Mary Lou
Published: November 2006

Although code optimizations are necessary to parallelize code, few guidelines exist for determining when and where to apply optimizations to produce the most efficient code. The order of applying optimizations can also have an impact on the efficiency of the final target code. However, determining the appropriate optimizations is difficult due to the complex interactions among the optimizations, scheduler and architecture. To aid in selecting appropriate optimizations, an optimizer generator (Genesis) is presented that produces an optimizer from specifications of optimizations. This paper describes the design and implementation of Genesis and demonstrates how such a generator could be used by optimizer designers. Some experiences with the generator are also described.
Using procedural parameters and continuations in combinatorial searches
Authors: Hwang Wen‐Ping , Wang Ching‐Lin
Published: November 2006

We use procedural parameters as a means to cut off unwanted branches in a search tree. The technique may be used to effect non‐blind backtracking. A recursive algorithm for generating all strings of n pairs of balanced parentheses is chosen as an illustrative example, since it cannot be formulated by conventional recursive backtracking.
On tuning the boyer‐moore‐horspool string searching algorithm
Authors: Smith P. D.
Published: November 2006

Experiments suggest that recently reported improvements to the Boyer‐Moore‐Horspool string searching algorithm may be due to compiler effects rather than to properties of the language being searched.
Simple authentication
Authors: Snow C. R. , Whitfield H.
Published: November 2006

This paper describes a simple authentication protocol for use with terminal emulation programs running on small workstations, and communicating with a host computer over a (potentially) insecure network. The technique has the advantage that it requires no more network traffic than would be necessary using a standard user‐id/password challenge, and also requires only a small amount of additional intelligence at the workstation. Some management issues are also discussed. The system has been implemented on two host systems and two workstation types.
The programming language superpascal
Authors: Hansen Per Brinch
Published: November 2006

This paper defines SuperPascal—a secure programming language for publication of parallel scientific algorithms. SuperPascal extends a subset of IEEE Standard Pascal with deterministic statements for parallel processes and synchronous message communication. A parallel statement denotes parallel execution of a fixed number of statements. A forall statement denotes parallel execution of the same statement by a dynamic number of processes. Recursive procedures may be combined with parallel and forall statements to define recursive parallel processes. Parallel processes communicate by sending typed messages through channels created dynamically. SuperPascal omits ambiguous and insecure features of Pascal. Restrictions on the use of variables enable a single‐pass compiler to check that parallel processes are disjoint, even if the processes use procedures with global variables.
Multimedia e‐mail: The evolution approach based on adapters
Authors: Huang Chung‐Ming , Lo Chung‐Ming
Published: November 2006

A lot of current e‐mail systems are ASCII text‐based, e.g. the e‐mail system in Internet. In the coming era of multimedia, e‐mails will be composed of other non‐text‐based information. This paper presents an evolution approach to enhance the capabilities of the current text‐based e‐mail systems. Using the proposed approach, an adapter is added to the top of the current system. As a result, multimedia e‐mails can be transmitted without changing the kernel part of the existing systems. We also propose an encoding scheme that has a 7/8 bandwidth utilization rate. Using this encoding scheme, all of the non‐ASCII data formats, e.g. image, voice, graphics, and so on, will be transformed to the ASCII data formats. Recently, we have developed an experimental multimedia e‐mail system using the proposed method. Our system has been developed on SUN SPARC workstations and an X‐window‐based user‐interface is provided in the system.
Optimizedk‐shortest‐paths algorithm for facility restoration
Authors: Macgregor M. H. , Grover W. D.
Published: November 2006

The problem of finding shortest paths arises in many contexts; testing restoration algorithms and developing design packages for large telecommunications networks are two cases where the simple task of finding sets of restoration paths can consume up to 95 per cent of the execution time of an application program. This paper presents experimental studies of several well‐known shortest‐paths algorithms adapted to the task of finding the k‐successively‐shortest link‐disjoint replacement paths for restoration in a telecommunications network with n nodes. The implementations range in complexity fromO(kn2) when based on Dijkstra's original method, through several improvements to an efficient implementation ofO(kn[v+longn]) complexity, and finally to anO(kn) implementation for the special case of edge‐sparse graphs with small integer edge weights. Here v is the maximum degree of a node in the network. Several alternatives were tested during the course of these studies, particularly with a view to minimizing the number of heap updates, These alternatives are possible because we are searching for several paths between a given pair of nodes, rather than just one path between one or more pairs of nodes. Two fairly straightforward changes yield a decrease in execution time, whereas a more complex heap management strategy consumes as much time in the added code as it releases from the main routine. Experimental results confirm the theoretical complexity of q k n log n) and demonstrate a speed‐up of nearly an order of magnitude over the simplerO(kn2) implementation in the largest networks tested. The optimized implementation is recommended for planning and operational applications of k‐shortest paths rerouting for telecommunications network restoration and restorable network design. If hop counts or small integer link weights can be used to measure distances, then the qkn) implementation is recommended, as typical telecommunications networks are edge‐sparse.
A message‐driven programming system for fine‐grain multicomputers
Authors: Maskit Daniel , Taylor Stephen
Published: November 2006

This paper describes an experimental message‐driven programming system for fine‐grain multicomputers. The initial target architecture is the J‐machine designed at MIT. This machine combines a unique collection of architectural features that include fine‐grain processes, on‐chip associative memory; and hardware support for process synchronization. The programming system uses these mechanisms via a simple message‐driven process model that blurs the distinction between processes and messages: messages correspond to processes that are executed elsewhere in the network. This model allows code and data to be distributed across the computers in the machine, and is supported at every stage of the program development cycle. The prototype system we have developed includes a basic set of programming tools to support the model; these include a compiler, linker, archiver, loader and microkernel. Although the concepts are language independent, our prototype system is based on GNU‐C.
A framework for execution monitoring in icon
Authors: Jeffery Clinton L. , Griswold Ralph E.
Published: November 2006

Execution monitors are widely used during software development for tasks that require an understanding of program behavior, such as debugging and profiling. The Icon programming language has been enhanced with a framework that supports execution monitoring. Under the enhanced translator and interpreter, neither source modification nor any special compiler command‐line option is required in order to monitor an Icon program. Execution monitors are written in the source language, instead of the implementation language. Performance, portability, and detailed access to the monitored program's state are achieved using a coroutine model and dynamic loading rather than the separate‐process model employed by many conventional monitoring systems.
DeViouS: A distributed environment for computer vision
Authors: Romig Phillip R. , Samal Ashok
Published: November 2006

Computer vision, owing to the size and complexity of its tasks and its importance to industrial and economic growth, was selected as one of the grand challenge problems by the U.S. Federal High Performance Computing Program. Integration of vision operations is identified as a key element of the challenge. A system to integrate computer vision in a distributed environment is presented here. This system, called DeViouS, is based on the client/server model and runs in a heterogeneous environment of Unix workstations. Modern computing environments include large numbers of high‐powered workstations connected by a very fast network. Many of these computers are idle most of the time. DeViouS takes advantage of this feature of computing environments to distribute the execution of vision tasks.

Two primary goals of DeViouS are to provide a practical distributed system and a research environment for vision computing. DeViouS is based on a modular design that allows experimentation in various aspects of algorithm design, scheduling and network programming. It can make use of any existing computer vision packages with very minor changes to DeViouS. DeViouS has been tested in an environment of SUN and Digital workstations and has shown substantial improvements in speed over sequential computing with negligible overhead.
Extending a functional programming system for embedded applications
Authors: Wallace Malcolm , Runciman Colin
Published: November 2006

Functional languages do not usually mesh well with embedded applications because of the need for special I/O device‐handling. By introducing a process model to a language, however, it becomes possible to express register‐level device operations and interrupts in a modular manner. This paper describes such a model, its implementation by extension to the Gofer programming system, and examples of its use. Performance results indicate that even this prototype interpretive system is adequate for small applications. The major gain of using a functional language is the ease with which abstraction can be layered over low‐level detail, improving both the readability of code and its tractability.
The long division algorithm of linger, mills and witt
Authors: Hansen Per Brinch
Published: November 2006

The long division algorithm of Linger, Mills and Witt is discussed and found to be significantly slower than a recent algorithm developed by the author.
Declarative specification of the architecture of a software development environment
Authors: Ambriola V. , Ciancarini P. , Corradini A.
Published: November 2006

There is an increasing interest in the study of software architectures; however, it still unclear which kind of formalisms and techniques should be used in their design. We study the suitability of a rule‐based, parallel logic language in the specification of the architecture of a complex software system, i.e. a software development environment. We have used as a case study SMILE, an environment for programming‐in‐the‐large. Because of the declarative, concurrent and object‐oriented features of parallel logic programming, we have been able to design a software architecture that emphasizes the dynamics of co‐ordination inside the software development environment. The result of this experience shows the usefulness and some weaknesses of logic languages for specifying and prototyping the software architecture of a distributed interactive system.
A flexible graphical user interface for performance modeling
Authors: Lin Yi‐Bing , Daly Dan
Published: November 2006

We identify three goals for the graphical user interface (GUI) of a network simulation environment: user friendliness, model re‐usability, and application extensibility. We address the user‐friendliness issue by proposing a simple yet efficient approach to setup parameters for the simulation models. We address the application extensibility issue with a two‐layer GUI architecture. The two layers are loosely coupled, and the first layer can be easily replaced without affecting the other components of the simulation environment. The concept of subnetwork is used to address the model reusability issue. Unlike most existing simulation packages, where a subnetwork is simply a method to group the nodes, the subnetwork construct in our approach is a first‐class citizen in the simulation environment (i.e., all operations for a basic node also apply to a subnetwork). The port concept is used to define the I/O relationship between a subnetwork and the outside world. Parameter dialog boxes are used to set up the parameters for a subnetwork conveniently. Finally, a simple stack mechanism is used to measure subnetwork‐wide output statistics.