bluuebunny/crossref_metadata_2025 huggingface dataset:
ACM SIGPLAN history of programming languages conference JOSS language summary
Authors: Baker Charles L.
Published: November 2005

JOSS is one of the earliest interactive, multi-user languages to become operational (the first demonstration was in 1963) and as such had a strong influence on many similar systems and languages which proliferated shortly thereafter. The system (hardware and software design and implementation) was developed by J. C. Shaw, T. O. Ellis, I. D. Nehama, A. Newell, and K. W. Uncapher at the RAND Corporation. The name is an acronym derived from:
JOHNNIAC
—the RAND-built Princeton-type computer named in honor of the mathematician John von Neumann;
OPEN SHOP
—designating operation by personnel other than those attached to the computing center; and
SYSTEM
—implying that JOSS is more than just a computer language.

At the time of initial system hardware specification, no acceptable typewriter-based terminals were commercially available, nor was the JOHNNIAC configured to accept multi-user input/output of this type. Therefore, special equipment was designed and built at RAND to meet these needs. The user terminal was based on the IBM model B typewriter, essentially equivalent to those used by RAND secretaries at that time. A special character set was specified to provide the symbols required by the JOSS language. Control and interface of up to eight remote consoles was provided by multiple-typewriter-control-system (MTCS) hardware. The development of these JOSS hardware components overlapped the development of the JOSS language.
A brief description of JOVIAL
Authors: Cheatham T. E.
Published: November 2005

JOVIAL (Jules' Own Version of the International Algebraic Language) was one of the first programming languages developed primarily to aid in programming large complex real time systems. Today it remains a major language for these applications and versions of JOVIAL have been implemented on dozens of different computers. The language and its compilers have been developed primarily by the Systems Development Corporation.

JOVIAL was based on Algol-58 but includes numerous features not in Algol (58 or 60) which make it particularly useful for programming large scale systems. The most important of these is the COMPOOL (communications POOL), a central repository of data descriptions which permits programmers to reference data items without concerns as to how they are represented on some particular computer.
The development of JOVIAL
Authors: Schwartz Jules I.
Published: November 2005

The time was late 1958. Computers that those who were involved with the first JOVIAL project had been using included the JOHNNIAC (built at Rand Corporation), the IBM AN/FSQ-7 (for SAGE), 701, and 704. A few had worked with board wired calculators. Some had never programmed. For those using IBM, the 709 was the current machine. There were various other manufacturers at the time, some of whom do not exist today as computer manufacturers.

The vacuum tube was still in vogue, Very large memories, either high speed direct access or peripheral storage, didn't exist, except for magnetic tape and drums on some computers.
A micro-manual for LISP - not the whole truth
Authors: McCarthy John
Published: November 2005

LISP data are symbolic expressions that can be either
atoms
of
lists. Atoms
are strings of letters and digits and other characters not otherwise used in LISP. A list consists of a left parenthesis followed by zero or more atoms or lists separated by spaces and ending with a right parenthesis. Examples: A, ONION, (), (A), (A ONION A), (PLUS B (TIMES X PI) 1), (CAR (QUOTE (A B))).

The LISP programming language is defined by rules whereby certain LISP expressions have other LISP expressions as
values
. The function called
value
that we will use in giving these rules is not part of the LISP language but rather part of the informal mathematical language used to define LISP. Likewise, the italic letters
e
and
a
(sometimes with subscripts) denote LISP expressions, the letter
v
(usually subscripted) denotes an atom serving as a variable, and the letter
f
stands for a LISP expression serving as a function name.
ACM SIGPLAN history of programming languages conference SIMULA language summary
Authors: Franta W. R.
Published: November 2005

SIMULA was conceived in the early sixties by Ole-Johan Dahl and Kristen Nygaard of the Norwegian Computing Center [3 ]. The most prevalent version of the language today is SlMULA-67 [1].

SIMULA was designed for system description and system simulation. A system in this case is a collection of interdependent elements with a common goal [4]. A natural way to simulate a system is to describe the life cycle scenarios of its elements. This approach combines the local attributes of elements and the protocols for inter-element communication into a single structure. Elements may exist for the duration of the simulation or be created and destroyed during its course.
ACM SIGPLAN history of programming languages conference SNOBOL language summary
Authors: Shapiro Michael D
Published: November 2005

The SNOBOL programming languages introduced or popularized most of the concepts of character string processing. The original SNOBOL had just one data type: a string of characters. It could appear in a program as a literal delimited by quotation marks, or as a value assigned to a variable:

PET = “MY CALICO CAT”

Concatenation, a basic string operation, forms a new string from two or more strings placed end to end:

MYPET = “HERE Is” PET “. ”
A history of the SNOBOL programming languages
Authors: Griswold Ralph E.
Published: November 2005

Development of the SNOBOL language began in 1962. It was followed by SNOBOL2, SNOBOL3, and SNOBOL4. Except for SNOBOL2 and SNOBOL3 (which were closely related), the others differ substantially and hence are more properly considered separate languages than versions of one language. In this paper historical emphasis is placed on the original language, SNOBOL, although important aspects of the subsequent languages are covered.
Hardware/software cooperation in the iAPX-432
Authors: Rattner Justin
Published: November 2005

The Intel iAPX-432 is an object-based microcomputer system with a unified approach to the design and use of its architecture, operating system, and primary programming language. The concrete architecture of the 432 incorporates hardware support for data abstraction, small protection domains, and language-oriented run-time environments. It also uses its object-orientation to provide hardware support for dynamic heap storage management, interprocess communication, and processor dispatching.

We begin with an overview of the 432 architecture so readers unfamiliar with its basic concepts will be able to follow the succeeding discussion without the need to consult the references. Following that, we introduce the various forms of hardware/software cooperation and the criteria by which a function or service is selected for migration. This is followed by several of the more interesting examples of hardware/software cooperation in the 432. A comparison of cooperation in the 432 with several contemporary machines and discussions of development issues, past and future, complete the paper.
An overview of the mesa processor architecture
Authors: Johnsson Richard K. , Wick John D.
Published: November 2005

This paper provides an overview of the architecture of the Mesa processor, an architecture which was designed to support the Mesa programming system [4]. Mesa is a high level systems programming language and associated tools designed to support the development of large information processing applications (on the order of one million source lines). Since the start of development in 1971, the processor architecture, the programming language, and the operating system have been designed as a unit, so that proper tradeoffs among these components could be made.
The 801 minicomputer
Authors: Radin George
Published: November 2005

This paper provides an overview of an experimental system developed at the IBM T. J. Watson Research Center. It consists of a running hardware prototype, a control program and an optimizing compiler. The basic concepts underlying the system are discussed as are the performance characteristics of the prototype. In particular, three principles are examined:

system orientation towards the pervasive use of high level language programming and a sophisticated compiler,

a primitive instruction set which can be completely hard-wired,

storage hierarchy and I/O organization to enable the CPU to execute an instruction at almost every cycle.
An architectural alternative to optimizing compilers
Authors: Harbison Samuel P.
Published: November 2005

Programming languages are designed to make
programming
productive. Computer architectures are designed to make
program execution
efficient. Although architectures should be designed with programming languages in mind, it may be as inappropriate to make the computer execute the programming language directly it is to make the programmer use machine language. It is the compiler's job to match the programming language and the computer architectures, and therefore making compiler's efficient and easy to write are important design goals of a complete hardware/software system. This paper summerizes research completed in 1980 [5] on a computer architecture,
TM
, that takes over some of the more burdensome tasks of optimizing compilers for high-level-languages (HLL's), performing these tasks dynamically during the execution of the object program. This is a different approach to making compilers efficient than is commonly taken; more common approaches include devising more efficient optimization algorithms[I], being clever about when to do optimizations [4], and building the compilers semiautomatically [6].
Direct execution of lisp on a list_directed architecture
Authors: Sansonnet J. P. , Castan M. , Percebois C. , Botella D. , Perez J.
Published: November 2005

We have defined a direct-execution model dedicated to non-numerical processing which is based upon an internal representation of source programs derived from LISP. This model provides good support for both sophisticated editing (syntactical parsing, tree manipulation, pretty-printing, ...) of conventional languages and artificial intelligence languages. A high level microprogramming language (LEM) was designed to write the interpreters and the editors. A hardware processor was built and a LISP interpreter, microprogrammed in LEM, has been operational since September 1980.

First, the influence of LISP on the LEM language and the architecture is discussed. At the LEM level, we will see that LISP has prompted the control constructs and the access functions to the tree-structured internal form. As for the architecture, we present the hardware implementation of a special garbage collector based upon reference counters.

In turn, the machine has influenced the implementation of LISP. We present here the structure of our LISP interpreter and we give evaluation measures dealing with size, development effort, speed; they prove that programming in LEM is easy, short to debug and very concise. Moreover, the speed of our LISP interpreter confirms that the architecture is very efficient for symbolic processing.
Empirical analysis of the mesa instruction set
Authors: Sweet Richard E. , Sandman James G.
Published: November 2005

This paper describes recent work to refine the instruction set of the Mesa processor. Mesa [8] is a high level systems implementation language developed at Xerox PARC during the middle 1970's. Typical systems written in Mesa are large collections of programs running on single-user machines. For this reason, a major design goal of the project has been to generate compact object programs.

The computers that execute Mesa programs are implementations of a stack architecture [5]. The instructions of an object program are organized into a stream of eight bit bytes. The exact complement into of instructions in the architecture has changed as the language and machine micro architecture have evolved.

In Sections 3 and 4, we give a short history of the Mesa instruction set and discuss the motivation for our most recent analysis of it. In Section 5, we discuss the tools and techniques used in this analysis. Section 6 shows the results of this analysis as applied to a large sample of approximately 2.5 million instruction bytes. Sections 7 and 8 give advice to others who might be contemplating similar analyses.
An analysis of a mesa instruction set using dynamic instruction frequencies
Authors: McDaniel Gene
Published: November 2005

The Mesa architecture is implemented on a variety of processors, and dynamic instruction frequency data for two programs is used to analyze the architecture in an implementation independent fashion.

The Mesa compiler allocates variables in an order based upon their static frequency of use, and measurements are provided that show that these static predictions predict run time usage as well. We provide an evaluation of the advantages and costs of Mesa's compact byte encoding, its reliance upon an evaluation stack, and its use of memory.

The Mesa language has evolved over time in a hardware environment oriented around 16-bit quantities with growing use of and accommodations to 32-bit quantities. The cost of emulating 32-bit data paths on a 16-bit machine is identified for a program that heavily exploits longer values.

Several potential areas for improving the execution speed of a Mesa processor with special purpose hardware are identified.
Firmware structure and architectural support for monitors, vertical migration and user microprogramming
Authors: Maekawa Mamoru , Sakamura Ken , Ishikawa Chiaki
Published: November 2005

This paper describes firmware and hardware support necessary for constructing easy-to-understand and high performance operating systems including language translators and interpreters. Basic principles are one-to-one correspondence between logical hierarchy and physical hierarchy, and vertical migration. Implementation of monitors in firmware and architectural support for it are discussed, and a sample system is shown. Architectural support for user microprogramming is then discussed and an example is shown. After a total system firmware structure is discussed, an experiment of vertical migration is described. It is shown that a proper selection of modules for migration is extremely important. It is suggested that the direction shown in this paper is one of future directions of computer systems.
Dynamic system specification
Authors: Balzer Robert M.
Published: November 2005

Our group is perhaps unique in that our approach to modeling dynamic systems has a strong heritage from all three fields represented at this workshop. Each of the fields has contributed four major concepts to our modeling approach.

From the Data Base field, we have adopted the idea of a single global model (data base) which defines the state of the system. Fully associative relations among typed atomic objects (no internal structure) constitute the entire state description. An information model (query language) is defined for extracting information from the state (such as one or all objects satisfying some description, or the truthfulness of some proposition). Finally, the model is updated via transactions, so that either the entire operation is completed successfully, or the state is unchanged.
The use of data type information in an interactive database environment
Authors: Buneman Peter , Winston Ira
Published: November 2005

Despite the enormous advances that have been made in the specification of data types and data models in the fields of programming languages, databases and artificial intelligence; there remain a number of problems in attempting to unify the various approaches to the formal description of data. The purpose of this brief paper is to examine these problems from the point (or points) of view of those people—designers, administrators, applications programmers, and end-users—whose main interest is with databases. In particular, we hope to display special concern for the tools provided for the end-user, who should be the final beneficiary of whatever advances are made.

In order to pin down some of these problems, it is worthwhile to attempt a definition of certain terms used in databases:

1. A
data model
(or
database management system
if one is describing an implementation) is a set of parameterized or “generic” data types.

2. A
database schema
is a set of data types that result from instantiating the generic types of the data model to produce a set of data types that describe the data to be stored.

3. A
database
is an instantiation of those types defined by a schema.
Integrating a database system and programming / information environment
Authors: Cattell R. G.G.
Published: November 2005

Vast differences in terminology aside, there is considerable overlap between work in knowledge representation, programming language data types, and database models. Our current work on the Cedar programming environment has necessitated integrating a number of ideas in these areas.

As part of the Cedar project in the Computer Science Lab at Xerox PARC, we have been constructing a database management system. The goal of the Cedar environment is to greatly increase our productivity by combining the best currently known principles from programming languages, programming tools, and user interfaces into a single integrated system. Cedar is based on the Mesa programming language [1]. The goal of our database subproject of Cedar is to provide a uniform prepackaged way to perform access to data structures, as contrasted to the current state of affairs in which Mesa programmers repeatedly re-invent the facilities we intend to provide to type, structure, index, link, robustly store, concurrently access, and cache data stored in the primary or secondary memory of one or more computers on a network.
Modelling concepts for reasoning about access to knowledge
Authors: King Jonathan J.
Published: November 2005

There is growing agreement about the usefulness of putting semantic database constraints into explicit form that can be manipulated by various database management programs. Indeed, this is a prerequisite for building
intelligent database mediators
. These are programs that perform the task of a good database analyst: to pose the most effective and easily processed queries to help solve a problem.
Semantic query optimization
is a technique to exploit semantic constraints for one aspect of intelligent database mediation: increasing retrieval efficiency. The technique is to use semantic constraints to transform a query into an equivalent one that can be processed more efficiently. Various kinds of semantic knowledge that can be used for this purpose are described.
Relativism and views in a conceptual data base model
Authors: Kreps Peter
Published: November 2005

The purpose of the Pingree Park Workshop was to bring together practitioners from the fields of Artificial Intelligence (AI), Database Management (DB), and Programming Languages (PL), to discover common issues, and to explore commonalities and differences in approaches to these issues. At the risk of being superficial let me try to summarily characterize the three fields and point to where I think they may fruitfully interact.

It seems to me that at its best, AI is an interdisciplinary science of cognition. It attempts to understand the bases for natural cognition, primarily by developing models of structures and processes that underlie cognition. By incorporation into interactive systems these models can be both exploited as artificially intelligent technology and explored for their adequacy in explaining natural cognition.
A data abstraction approach to database modelling
Authors: Leavenworth B.
Published: November 2005

Attempts have been made for some time to reconcile the notions of data base modelling and data abstraction. Considering the overlapping concepts of information hiding and encapsulation from the data abstraction world, and data independence from the database world, it should not be necessary to design yet another programming language as others have done, specialized to a particular data model. Instead, the starting point for our work has been the proposition that an extant general purpose language providing data abstractions should be able to accommodate the popular data models by serving both as a data definition and manipulation language. The criticism has been made that while abstract data types hide the representation details, they also suppress the semantic structure of the data. While this may be true for “programming in the small” [2], it is not the case for “programming in the large” [2]. We will briefly indicate how a CLU-like language [4] (hereafter called XPLS) with minor extensions, plus its supporting module interconnection language (hereafter called the External Structure) can be used as a data-base definition and manipulation language. XPLS has been designed as a front end to PL/I and is supported by a preprocessor to the PL/I compiler. It turns out that XPLS plus External Structure supports and meshes more smoothly with a semantic data model (for example: [1], [3],[5], [6]) than with the older data models. Our work differs from a number of recent specialized languages which exploit data abstractions and strong type checking but which are based on the relation as a primitive data type. Our approach is not based on any particular data model.
Incompleteness in knowledge bases
Authors: Levesque Hector J.
Published: November 2005

The first topic for discussion at the High Level Abstraction Workshop was

What should be modelled?

that is, what aspects of the world (slice of reality / enterprise) must be dealt with in a high level conceptual model. I would like to address this question from the point of view of incomplete knowledge bases. Although my remarks pertain mainly to AI applications, I suspect that any application using an information system of some sort will eventually have to face similar issues.

The knowledge bases required in many applications can be characterized by a lack of complete information about the world of interest.
Abstract data types and Data Bases
Authors: Paolini Paolo
Published: November 2005

Several researchers have been working, recently, at the attempt of using the ADT approach in the Data Base area. Different specific problems have attacked and we will review some of them.
Are data types universal modelling concepts for data base systems?
Authors: Weber Herbert
Published: November 2005

Modelling encompasses two intellectual tasks: (1) the perception of some reality and (2) the representation of the perceived reality in accordance to a given model (obviously is a representation once again some kind of reality and hence subject to another representation in accordance to another model or notation). Because of human beings limited capabilities to perceive and completely and correctly represent reality any representation is an abstraction of the reality.

A representation in accordance to a given model is of course constrained by that model. Any facet of reality not representable with the model cannot be represented at all. Moreover any model constrains at the very same time the perception capabilities as well. Experience verifies that knowledge of a model tends to force the modeller to model according to this model even though it may not result in the most accurate representation. These two facts speak against an universal model but makes for a variety of models for different purposes. It is common practice for the representation of the reality in data bases to apply different models for the conceptual description of data bases or to apply different kinds of models for the physical description of data bases, etc.
Types, algebras and modeling
Authors: Zilles Stephen N.
Published: November 2005

Programming languages, database systems and artificial intelligence systems all have the notion that entities can be classified into
types
. As might be expected, however, the usage of the notion of type is not the same throughout or even within these areas. In this paper, I propose a notion of typing that is derived from work on programming languages and indicate how this notion might be used in the context of database systems. Thus, the paper is a step toward unifying the notions of type in data-bases and programming languages.
Threading Lisp
Authors: Nordstrom D. J.
Published: November 2005

An interpreter for Lisp based on the Forth model is described: Lisp and Forth are compared, threaded interpreters are discussed, and aspects of a Lisp implementation are presented.
Toward integration of the imperative and logic programming paradigms: Horn-clause programming in the Pascal environment
Authors: Radensky A.
Published: November 2005

This paper introduces a method for integrating the imperative and logic programming paradigms. The integration is implemented in the framework of a language named Paslog. Paslog is an extension of Pascal; it supports Horn clause programming in the Pascal environment. An experimental implementation and some properties of Paslog are discussed.
Fast partial evaluation of pattern matching in strings
Authors: Ager Mads Sig , Danvy Olivier , Rohde Henning Korsholm
Published: November 2005

We show how to obtain all of Knuth, Morris, and Pratt's linear-time string matcher by partial evaluation of a quadratic-time string matcher with respect to a pattern string. Although it has been known for 15 years how to obtain this linear matcher by partial evaluation of a quadratic one, how to obtain it
in linear time
has remained an open problem.Obtaining a linear matcher by partial evaluation of a quadratic one is achieved by performing its backtracking at specialization time and memoizing its results. We show (1) how to rewrite the source matcher such that its static intermediate computations can be shared at specialization time and (2) how to extend the memoization capabilities of a partial evaluator to static functions. Such an extended partial evaluator, if its memoization is implemented efficiently, specializes the rewritten source matcher in linear time.
Implementing typeful program transformations
Authors: Chen Chiyan , Xi Hongwei
Published: November 2005

The notion of program transformation is ubiquitous in programming language studies on interpreters, compilers, partial evaluators, etc. In order to implement a program transformation, we need to choose a representation in the meta language, that is, the programming language in which we construct programs, for representing object programs, that is, the programs in the object language on which the program transformation is to be performed. In practice, most representations chosen for typed object programs are typeless in the sense that the type of an object program cannot be reflected in the type of its representation. This is unsatisfactory as such typeless representations make it impossible to capture in the type system of the meta language various invariants in a program transformation that are related to the types of object programs. In this paper, we propose an approach to implementing program transformations that makes use of a first-order typeful program representation formed in Dependent ML (DML), where the type of an object program as well as the types of the free variables in the object program can be reflected in the type of the representation of the object program. We introduce some programming techniques needed to handle this typeful program representation, and then present an implementation of a CPS transform function where the relation between the type of an object program and that of its CPS transform is captured in the type system of DML. In a broader context, we claim to have taken a solid step along the line of research on constructing certifying compilers.
Slicing java programs that throw and catch exceptions
Authors: Allen Matthew , Horwitz Susan
Published: November 2005

Exceptions are the preferred method for error handling in object-oriented languages like Java. Current program-slicing algorithms do not correctly deal with exception-handling constructs, because they do not account for the additional control and data dependences introduced by exceptions. This paper extends previous work on program slicing using the system dependence graph (SDG) to support slicing programs with exceptions.
CodeBricks
Authors: Attardi Giuseppe , Cisternino Antonio , Kennedy Andrew
Published: November 2005

We present a framework for code generation that allows programs to manipulate and generate code at the source level while the joining and splicing of executable code is carried out automatically at the intermediate code/VM level. The framework introduces a data type Code to represent code fragments: methods/operators from this class are used to reify a method from a class, producing its representation as an object of type Code. Code objects can be combined by partial application to other Code objects. Code combinators, corresponding to higher-order methods, allow splicing the code of a functional actual parameter into the resulting Code object.
CodeBricks
is a library implementing the framework for the .NET Common Language Runtime. The framework can be exploited by language designers to implement metaprogramming, multistage programming and other language features. We illustrate the use of the technique in the implementation of a fully featured regular expression compiler that generates code emulating a finite state automaton. We present benchmarks comparing the performance of the RE matcher built with CodeBricks with the hand written one present in .NET.
Extending sized type with collection analysis
Authors: Chin Wei-Ngan , Khoo Siau-Cheng , Xu Dana N.
Published: November 2005

Many program optimizations and analyses, such as array-bounds checking, termination analysis, depend on knowing the size of a function's input and output. However, size information can be difficult to compute. Firstly, accurate size computation requires detecting a size relation between different inputs of a function. Secondly, size information may also be contained inside a collection (data structure with multiple elements). In this paper, we introduce some techniques to derive universal and existential size properties over collections of elements of recursive data structures. We shall show how a mixed constraint system could support the enhanced size type, and highlight examples where collection analysis are useful.
Toward efficient and robust software speculative parallelization on multiprocessors
Authors: Cintra Marcelo , Llanos Diego R.
Published: November 2005

With speculative parallelization, code sections that cannot be fully analyzed by the compiler are aggressively executed in parallel. Hardware schemes are fast but expensive and require modifications to the processors and memory system. Software schemes require no extra hardware but can be inefficient.This paper proposes a new software-only speculative parallelization scheme. The scheme is developed after a systematic evaluation of the design options available and is shown to be efficient and robust and to outperform previously proposed schemes. The novelty and performance advantage of the scheme stem from the use of carefully tuned data structures, synchronization policies, and scheduling mechanisms. Experimental results show that our scheme has small overheads and, for applications with few or no data dependence violations, realizes on average 71% of the speedup of a manually parallelized version of the code, outperforming two recently proposed software-only speculative parallelization schemes. For applications with many data dependence violations, our performance monitors and switches can effectively curb the performance degradation.
Compiler support for speculative multithreading architecture with probabilistic points-to analysis
Authors: Chen Peng-Sheng , Hung Ming-Yu , Hwang Yuan-Shin , Ju Roy Dz-Ching , Lee Jenq Kuen
Published: November 2005

Speculative multithreading (SpMT) architecture can exploit thread-level parallelism that cannot be identified statically. Speedup can be obtained by speculatively executing threads in parallel that are extracted from a sequential program. However, performance degradation might happen if the threads are highly dependent, since a recovery mechanism will be activated when a speculative thread executes incorrectly and such a recovery action usually incurs a very high penalty. Therefore, it is essential for SpMT to quantify the degree of dependences and to turn off speculation if the degree of dependences passes certain thresholds. This paper presents a technique that quantitatively computes dependences between loop iterations and such information can be used to determine if loop iterations can be executed in parallel by speculative threads. This technique can be broken into two steps. First probabilistic points-to analysis is performed to estimate the probabilities of points-to relationships in case there are pointer references in programs, and then the degree of dependences between loop iterations is computed quantitatively. Preliminary experimental results show compiler-directed thread-level speculation based on the information gathered by this technique can achieve significant performance improvement on SpMT.
Improving server software support for simultaneous multithreaded processors
Authors: McDowell Luke K. , Eggers Susan J. , Gribble Steven D.
Published: November 2005

Simultaneous multithreading (SMT) represents a fundamental shift in processor capability. SMT's ability to execute multiple threads simultaneously within a single CPU offers tremendous potential performance benefits. However, the structure and behavior of software affects the extent to which this potential can be achieved. Consequently, just like the earlier arrival of multiprocessors, the advent of SMT processors prompts a needed re-evaluation of software that will run on them. This evaluation is complicated, since SMT adopts architectural features and operating costs of both its predecessors (uniprocessors and multiprocessors). The crucial task for researchers is to determine which software structures and policies - multi-processor, uniprocessor, or neither - are most appropriate for SMT.This paper evaluates how SMT's changes to the underlying hardware affects server software, and in particular, SMT's effects on memory allocation and synchronization. Using detailed simulation of an SMT server implemented in three different thread models, we find that the default policies often provided with multiprocessor operating systems produce unacceptably low performance. For each area that we examine, we identify better policies that combine techniques from both uniprocessors and multi-processors. We also uncover a vital aspect of multi-threaded synchronization (interaction with operating system thread scheduling) that previous research on SMT synchronization had overlooked. Overall, our results demonstrate how a few simple changes to applications' run-time support libraries can dramatically boost the performance of multi-threaded servers on SMT, without requiring modifications to the applications themselves.
Programming the FlexRAM parallel intelligent memory system
Authors: Fraguela Basilio B. , Renau Jose , Feautrier Paul , Padua David , Torrellas Josep
Published: November 2005

In an intelligent memory architecture, the main memory of a computer is enhanced with many simple processors. The result is a highly-parallel, heterogeneous machine that is able to exploit computation in the main memory. While several instantiations of this architecture have been proposed, the question of how to effectively program them with little effort has remained a major challenge.In this paper, we show how to effectively hand-program an intelligent memory architecture at a high level and with very modest effort. We use FlexRAM as a prototype architecture. To program it, we propose a family of
high-level compiler directives
inspired by OpenMP called
CFlex
. Such directives enable the processors in memory to execute the program in cooperation with the main processor. In addition, we propose libraries of highly-optimized functions called
Intelligent Memory Operations (IMOs)
. These functions program the processors in memory through CFlex, but make them completely transparent to the programmer. Simulation results show that, with CFlex and IMOs, a server with 64 simple processors in memory runs on average 10 times faster than a conventional server. Moreover, a set of conventional programs with 240 lines on average are transformed into CFlex parallel form with only 7 CFlex directives and 2 additional statements on average.
QR factorization with Morton-ordered quadtree matrices for memory re-use and parallelism
Authors: Frens Jeremy D. , Wise David S.
Published: November 2005

Quadtree matrices using Morton-order storage provide natural blocking on every level of a memory hierarchy. Writing the natural recursive algorithms to take advantage of this blocking results in code that honors the memory hierarchy without the need for transforming the code. Furthermore, the divide-and-conquer algorithm breaks problems down into independent computations. These independent computations can be dispatched in parallel for straightforward parallel processing.Proof-of-concept is given by an algorithm for
QR
factorization based on Givens rotations for quadtree matrices in Morton-order storage. The algorithms deliver positive results, competing with and even beating the LAPACK equivalent.
Hybrid dynamic data race detection
Authors: O'Callahan Robert , Choi Jong-Deok
Published: November 2005

We present a new method for dynamically detecting potential data races in multithreaded programs. Our method improves on the state of the art in accuracy, in usability, and in overhead. We improve accuracy by combining two previously known race detection techniques --
lockset-based detection and happens-before-based detection
-- to obtain fewer false positives than lockset-based detection alone. We enhance usability by reporting more information about detected races than any previous dynamic detector. We reduce overhead compared to previous detectors -- particularly for large applications such as Web application servers -- by not relying on happens-before detection alone, by introducing a new optimization to discard redundant information, and by using a "two phase" approach to identify error-prone program points and then focus instrumentation on those points. We justify our claims by presenting the results of applying our tool to a range of Java programs, including the widely-used Web application servers Resin and Apache Tomcat. Our paper also presents a formalization of locksetbased and happens-before-based approaches in a common framework, allowing us to prove a "folk theorem" that happens-before detection reports fewer false positives than lockset-based detection (but can report more false negatives), and to prove that two key optimizations are correct.
Using generative design patterns to generate parallel code for a distributed memory environment
Authors: Tan Kai , Szafron Duane , Schaeffer Jonathan , Anvik John , MacDonald Steve
Published: November 2005

A design pattern is a mechanism for encapsulating the knowledge of experienced designers into a re-usable artifact. Parallel design patterns reflect commonly occurring parallel communication and synchronization structures. Our tools, CO2P3S (Correct Object-Oriented Pattern-based Parallel Programming System) and MetaCO2P3S, usegenerative design patterns. A programmer selects the parallel design patterns that are appropriate for an application, and then adapts the patterns for that specific application by selecting from a small set of code-configuration options. CO2P3S then generates a custom framework for the application that includes all of the structural code necessary for the application to run in parallel. The programmer is only required to write simple code that launches the application and to fill in some application-specific sequential hook routines. We use generative design patterns to take an application specification (parallel design patterns + sequential user code) and use it to generate parallel application code that achieves good performance in shared memory and distributed memory environments. Although our implementations are for Java, the approach we describe is tool and language independent. This paper describes generalizing CO2P3S to generate distributed-memory parallel solutions.
ARMI
Authors: Saunders Steven , Rauchwerger Lawrence
Published: November 2005

ARMI is a communication library that provides a framework for expressing fine-grain parallelism and mapping it to a particular machine using shared-memory and message passing library calls. The library is an advanced implementation of the RMI protocol and handles low-level details such as scheduling incoming communication and aggregating outgoing communication to coarsen parallelism when necessary. These details can be tuned for different platforms to allow user codes to achieve the highest performance possible without manual modification. ARMI is used by STAPL, our generic parallel library, to provide a portable, user transparent communication layer. We present the basic design as well as the mechanisms used in the current Pthreads/OpenMP, MPI implementations and/or a combination thereof. Performance comparisons between ARMI and explicit use of Pthreads or MPI are given on a variety of machines, including an HP V2200, SGI Origin 3800, IBM Regatta-HPC and IBM RS6000 SP cluster.
The design of the C++ Booch Components
Authors: Booch Grady , Vilot Michael
Published: November 2005

This paper describes design issues encountered developing a reusable component library. The design applied encapsulation, inheritance, composition and type parameterization. The implementation uses various C++ mechanisms, including: virtual and static member functions, templates, and exceptions.

The resulting library contains about 500 components (mostly template classes and functions) and an optional utility for instantiating templates. The components provide variations of basic collection/container abstractions with various time and space complexities.

A key insight gained from this project: the design process centered on developing a “template for the templates” — designing a component framework and orderly process for generating the template classes.
Viewing object as patterns of communicating agents
Authors: Nierstrasz Oscar , Papathomas Michael
Published: November 2005

Following our own experience developing a concurrent object-oriented language as well of that of other researchers, we have identified several key problems in the design of a concurrency model compatible with the mechanisms of object-oriented programming. We propose an approach to language design in which an executable notation describing the behaviour of communicating agents is extended by syntactic patterns that encapsulate language constructs. We indicate how various language models can be accommodated, and how mechanisms such as inheritance can be modeled. Finally, we introduce a new notion of types that characterizes concurrent objects in terms of their externally visible behaviour.
A logical theory of concurrent objects
Authors: Meseguer José
Published: November 2005

A new theory of concurrent objects is presented. The theory has the important advantage of being based directly on a logic called
rewriting logic
in which concurrent object-oriented computation exactly corresponds to logical deduction. This deduction is performed by
concurrent rewriting
modulo structural axioms of associativity, commutativity and identity that capture abstractly the essential aspects of communication in a distributed object-oriented configuration made up of concurrent objects and messages. Thanks to this axiomatization, it becomes possible to study the behavior of concurrent objects by formal methods in a logic intrinsic to their computation. The relationship with Actors and with other models of concurrent computation is also discussed. A direct fruit of this theory is a new language, called Maude, to program concurrent object-oriented modules in an entirely declarative way using rewriting logic; modules written in this language are used to illustrate the main ideas with examples. Maude contains OBJ3 as a functional sublanguage and provides a simple and semantically rigorous integration of functional programming and concurrent object-oriented programming.
Type substitution for object-oriented programming
Authors: Palsberg Jens , Schwartzbach Michael I.
Published: November 2005

Genericity allows the substitution of types in a class. This is usually obtained through parameterized classes, although they are inflexible since any class can be inherited but is not in itself parameterized. We suggest a new genericity mechanism,
type substitution
, which is a subclassing concept that complements inheritance: any class is generic, can be “instantiated” gradually without planning, and has all of its generic instances as subclasses.
A parallel object-oriented language with inheritance and subtyping
Authors: America Pierre , van der Linden Frank
Published: November 2005

This paper shows that inheritance and subtyping can be introduced advantageously into a parallel object-oriented language, POOL-I. These concepts are clearly distinguished, because they deal with different aspects of programming. In this way several problems traditionally adhering to inheritance can be solved. The language POOL-I is a parallel object-oriented language with a strong typing scheme which includes genericity and dynamic binding. A novel and particularly powerful mechanism offers the possibility to manipulate and analyse types dynamically.
Contracts: specifying behavioral compositions in object-oriented systems
Authors: Helm Richard , Holland Ian M. , Gangopadhyay Dipayan
Published: November 2005

Behavioral compositions, groups of interdependent objects cooperating to accomplish tasks, are an important feature of object-oriented systems. This paper introduces
Contracts
, a new technique for specifying behavioral compositions and the obligations on participating objects. Refinement and composition of contracts allows for the creation of large grain abstractions based on behavior, orthogonal to those provided by existing class constructs. Using contracts thus provides a basis and vocabulary for
Interaction-Oriented
design which greatly facilitates the early identification, abstraction and reuse of patterns of behavior in programs. Contracts differ from previous work in that they capture explicitly and abstractly the behavioral dependencies amongst cooperating objects. By explicitly stating these dependencies, contract also provide an effective aid for program understanding and reuse.
Reasoning about object-oriented programs that use subtypes
Authors: Leavens Gary T. , Weihl William E.
Published: November 2005

Programmers informally reason about object-oriented programs by using subtype relationships to classify the behavior of objects of different types and by letting supertypes stand for all their subtypes. We describe formal specification and verification techniques for such programs that mimic these informal ideas. Our techniques are modular and extend standard techniques for reasoning about programs that use abstract data types. Semantic restrictions on subtype relationships guarantee the soundness of these techniques.
Object-oriented real-time language design: constructs for timing constraints
Authors: Ishikawa Yutaka , Tokuda Hideyuki
Published: November 2005

We propose a new object-oriented programming language called RTC++ for programming real-time applications. RTC++ is an extension of C++ and its features are to specify i) a real-time object which is an active entity, ii) timing constraints in an operation as well as in statements, and iii) a periodic task with rigid timing constraints.

In this paper, we first discuss real-time programming issues and what language support should be provided for building real-time applications. Then, the key features of RTC++ are described. Some programming examples are shown to demonstrate RTC++'s expressive power. A comparison to other programming languages are also discussed.