bluuebunny/crossref_metadata_2025 huggingface dataset:
CORBA vs. Ada 95 DSA
Authors: Kermarrec Yvon
Published: October 2004

Recent evolutions in computer networks have made it possible to consider distributed platforms as possible architectures for numerous applications. The classes of distributed applications are numerous and go from time consuming application (performance quest) to geographically distributed applications through safety and critical softwares. As beforehand, hardware evolutions have been fast paced and much earlier than software techniques to build applications on these distributed targets. In this paper, we shall investigate and compare three different approaches: the language approach of Ada 95 for distributed systems vs. two distributed platforms. And for this evaluation, we shall take the developer's view, that is to go beyond the technical response but to take into account the developer of the distributed application.
Applying Ada, Java and CORBA for making a command and control information system platform independent
Authors: Bühler Gerhard , Faßbender Heinz
Published: October 2004

In this paper, we describe our experiences in applying CORBA and Java while redesigning an experimental command and control information system that is programmed in Ada 83. Our goal was to allow the user to use the system from any platform with minimal requirements to system resources.
Ada conformity assessments
Authors: Tonndorf Michael
Published: October 2004

This paper presents the actual status of Ada Conformity Assessments after the transition of Ada Conformity Assessments from the Ada Joint Program Office to ISO. The principles of Ada Conformity Assessments according to the ISO/IEE Final Committee Draft 18009 are summarized and the commonalties and differences to the previous practices are discussed. In the main part of the work conformity assessments for Ada C, C++, and Java are compared. It is shown that the process as practiced with Ada is unique compared to other programming languages. This can be understood by looking at the special culture of the language Ada and its validation system. Both were sponsored by one single party (the US DoD) and not the IT industry. The paper concludes with an assessment and outlook on the future development on compiler conformity assessments in general.
Interfacing low-level C device drivers with Ada 95
Authors: Doran Steven
Published: October 2004

The personal computer hardware marketplace has grown rapidly in recent years. Many software projects, as a cost-cutting measure, are buying "off-the-self" items to meet heir hardware requirements. Almost all of the device drivers for these devices are written in the C programming language. However, the selection of the programming language for the project does not need to be confined to C. This paper details the powerful tools in Ada 95, such as pragmas to interface code written in other programming languages to Ada 95 applications. An example of a generic real-time Ada 95 application interfacing with a low-level C serial device driver is used to aid the reader in the concepts and idea's discussed in the paper.
Integrating a software engineering approach into an Ada closed laboratory
Authors: Wang Ming
Published: October 2004

A manual for a closed laboratory incorporating software engineering concepts was developed and implemented for Ada'95 during the 1998-1999 academic year. The software engineering concepts were applied during the development and implementation. The purpose was to teach student programmers (and prospective software engineers) disciplined methods for developing software. The findings were: 1. the closed laboratory provided an ideal environment for students to explore, learn and implement software development methods as well as learn the Ada language. 2. The closed laboratory was a major contributor for students to understand the course contents and built a bridge between the class lectures and open lab projects. 3. The closed laboratory helped students to accomplish their open lab projects in a more efficient and professional way by following software development methods. A survey conducted at the end of the semester indicated the success of implementation of software development methods in the Ada closed laboratory. The responses showed that students enjoyed the closed laboratory and considered it an exciting and interesting learning experience.
The role of distributed, real-time Ada & C++ on the Airborne Surveillance Testbed (AST) program
Authors: Lortz Henry A. , Tibbetts Timothy A.
Published: October 2004

The Airborne Surveillance Testbed (AST) program, managed by SMDC for BMDO, is a technology demonstration program that supports development, test, and evaluation of defensive systems to counter intercontinental and theater ballistic missiles (ICBMs and TBMs) and their warheads. The heart of the AST program is a Boeing 767 aircraft equipped with a Raytheon-built, large-aperture, multiband, high data rate infrared sensor and a wide variety of processing equipment designed to detect, track, and discriminate ballistic missiles at long ranges. A Raytheon interceptor seeker (part of a Navy risk reduction effort) has recently been integrated onto the aircraft; a staring medium wave infrared (MWIR) camera is currently being added as well. Onboard processing capabilities include a Concurrent TurboHawk (multi-CPU PowerPC flight computer) along with a variety of custom and off-the-shelf signal processing equipment, SGI workstations, DEC Alphas, and PCs, largely programmed in Ada and C++. These systems are linked via SCRAMNet, Ethernet, 1553B, RS422 and RS232, and communicate externally via various radio systems. Since the start of the program in 1984, AST has been making use of Ada83, Ada95, and C++ for both simulations and embedded flight software. During that time, we have gathered a lot of experience in the use of Ada for real-time distributed systems, especially concerning:• The pitfalls of task scheduling algorithms and priorities• The benefits of the (careful) use of generics• The importance of some changes between Ada83 and Ada95• Interfacing Ada software to hardware (and standardized interrupt handling)• The importance of proper use of exception handling to ensure fault tolerance
Scheduling problems for parallel and distributed systems
Authors: Rusanova Olga , Korochkin Alexandr
Published: October 2004

A two-pass scheduling algorithm for parallel and distributed computer systems is presented in this paper. We consider this algorithm as a complex of two stages: process queue formation and assignment procedure. A new approach of both stages realization is proposed. Our algorithm can be used to increase efficiency of static and dynamic scheduling.
What happened to integrated environments? (panel session)
Authors: Boehm Barry , Taft S. Tucker , Wasserman Tony
Published: October 2004

20 years ago, in 1979, a landmark community-wide process was launched to establish notional requirements for integrated software engineering environments. The resulting "Stoneman" document was published in February 1980. Bred of the software engineering research community and catalyzed by the Government Ada sponsor, this "integrated environment movement" branched out and was embraced widely in the software engineering community in the 1980's as a needed, achievable, centrist approach to accelerate the benefits of disciplined software engineering into mainstream practice. The CASE tool industry bloomed as products integrating lifecycle activities and artifacts emerged, and research evolved to environments integrated by support for emerging, maturing notions of software processes. Yet, at the end of the 1990's, this movement appears to have virtually died, and more and more production software organizations are instead (or again) using old-fashioned stand-alone development tools and struggling to match up tools and their outputs and inputs to do software engineering. The purpose of this panel is to explore the reasons why the integrated environment movement has retreated, whether the recent tools and methods are or are not achieving the goals of integrated environments, whether those goals have been superceded by other goals better served without integrated environments, and what these examinations indicate about future requirements and research needs.
Building reliable, high-performance communication systems from components
Authors: Liu Xiaoming , Kreitz Christoph , van Renesse Robbert , Hickey Jason , Hayden Mark , Birman Kenneth , Constable Robert
Published: October 2004

Although building systems from components has attractions, this approach also has problems. Can we be sure that a certain configuration of components is correct? Can it perform as well as a monolithic system? Our paper answers these questions for the Ensemble communication architecture by showing how, with help of the Nuprl formal system, configurations may be checked against specifications, and how optimized code can be synthesized from these configurations. The performance results show that we can substantially reduce end-to-end latency in the already optimized Ensemble system. Finally, we discuss whether the techniques we used are general enough for systems other than communication systems.
Separating key management from file system security
Authors: Mazières David , Kaminsky Michael , Kaashoek M. Frans , Witchel Emmett
Published: October 2004

No secure network file system has ever grown to span the Internet. Existing systems all lack adequate key management for security at a global scale. Given the diversity of the Internet, any particular mechanism a file system employs to manage keys will fail to support many types of use.We propose separating key management from file system security, letting the world share a single global file system no matter how individuals manage keys. We present SFS, a secure file system that avoids internal key management. While other file systems need key management to map file names to encryption keys, SFS file names effectively contain public keys, making them
self-certifying pathnames.
Key management in SFS occurs outside of the file system, in whatever procedure users choose to generate file names.Self-certifying pathnames free SFS clients from any notion of administrative realm, making inter-realm file sharing trivial. They let users authenticate servers through a number of different techniques. The file namespace doubles as a key certification namespace, so that people can realize many key management schemes using only standard file utilities. Finally, with self-certifying pathnames, people can bootstrap one key management mechanism using another. These properties make SFS more versatile than any file system with built-in key management.
EROS
Authors: Shapiro Jonathan S. , Smith Jonathan M. , Farber David J.
Published: October 2004

EROS is a capability-based operating system for commodity processors which uses a single level storage model. The single level store's persistence is transparent to applications. The performance consequences of support for transparent persistence and capability-based architectures are generally believed to be negative. Surprisingly, the basic operations of EROS (such as IPC) are generally comparable in cost to similar operations in conventional systems. This is demonstrated with a set of microbenchmark measurements of semantically similar operations in Linux.The EROS system achieves its performance by coupling well-chosen abstract objects with caching techniques for those objects. The objects (processes, nodes, and pages) are well-supported by conventional hardware, reducing the overhead of capabilities. Software-managed caching techniques for these objects reduce the cost of persistence. The resulting performance suggests that composing protected subsystems may be less costly than commonly believed.
EMERALDS
Authors: Zuberi Khawar M. , Pillai Padmanabhan , Shin Kang G.
Published: October 2004

EMERALDS (Extensible Microkernel for Embedded, ReAL-time, Distributed Systems) is a real-time microkernel designed for small-memory embedded applications. These applications must run on slow (15-25MHz) processors with just 32-128 kbytes of memory, either to keep production costs down in mass-produced systems or to keep weight and power consumption low. To be feasible for such applications, the OS must not only be small in size (less than 20 kbytes), but also have low-overhead kernel services. Unlike commercial embedded OSs which rely on carefully-crafted code to achieve efficiency, EMERALDS takes the approach of re-designing the basic OS services of task scheduling, synchronization, communication, and system call mechanism by using characteristics found in small-memory embedded systems, such as small code size and
a priori
knowledge of task execution and communication patterns. With these new schemes, the overheads of various OS services are reduced 20-40% without compromising any OS functionality.
Issues in optimizing Ada code
Authors: Rosenfeld David , Ryer Mike
Published: October 2004

This paper presents a summary of the aspects of Ada that make optimization more difficult than for simpler languages such as C. Points made are that Ada is low in "distributed overhead" but that this is only so if compilers are very careful to ensure it; and that more optimization is needed for Ada than for other languages. Specific language features and their impact on code generation and optimization are discussed. Some suggestions for developing effective Ada benchmarks are provided.
Hartstone
Authors: Weiderman Nelson
Published: October 2004

The purpose of this paper is to define the operational concept for a series of benchmark requirements to be used to test the ability of a system to handle hard real-time applications. Implementations of such benchmarks would be useful in evaluating scheduling algorithms, protocols, and design paradigms, as well as processors, languages, compilers, and operating systems. Several Ada programs are under development to test standard versions of the benchmark requirements and will be released into the public domain.
Some problems in distributing real-time Ada programs across machines
Authors: Volz Richard A. , Mudge Trevor N. , Naylor Arch W. , Mayer John H.
Published: October 2004

The Ada Research Group of the Robotics Research Laboratory at The University of Michigan is currently developing a real-time distributed computing capability based upon the premises that real-time distributed
languages
provide the best approach to real-time distributed computing and, given the focus on the language level, that Ada offers an excellent candidate language. The first phase of the group's work was on analysis of real-time distributed computing. The second, and current, phase is the development of a pretranslator which translates an Ada program into n Ada programs, each being targeted for one of a group of processors and each having required communication support software automatically created and attached by the pre-translator. This paper describes the pretranslator being developed and a number of issues which have arisen with regard to the distributed execution of a single Ada program, including language semantics, objects of distribution and their mutual access, network timing, and execution environments.
Execution monitoring and debugging tool for Ada using relational algebra
Authors: Di Maio A. , Ceri S. , Crespi Reghizzi S.
Published: October 2004

This symbolic run-time debugger for Ada provides facilities for observing and manipulating the execution of a monitored program, also for concurrent aspects. The debugger can be used interactively, and also as a monitoring program to control the application. A feature of this project is the use of relational algebra for defining compiler and kernel interfaces and for handling debugger information. The implementation is based on an Ada task to interface with the debugging operator and a set of user-defined Ada monitoring tasks. A prototype of the debugger was completed as a part of ART, a relational translator and interpreter for Ada.
The Ravenscar Tasking Profile—experience reporting
Authors: Dobbing Brian , Romanski George
Published: October 2004

The Ravenscar Profile was defined at the 18
th
International Real-Time Ada Workshop as a simple subset of the tasking features of Ada, in order to support efficient, high integrity applications that need to be analysed for their timing properties. Ada compiler vendor Aonix subsequently implemented the Profile via its Raven product line, and is currently engaged in producing the formal certification material for qualifying the runtime system to the most stringent set of guidelines --- DO-178B Level A. This paper describes some of the experiences in implementing and qualifying the Profile, and some early indications from the user community of its value to address the application domains that it was intended for.
Transparent replication for fault tolerance in distributed Ada 95
Authors: Wolf Thomas
Published: October 2004

In this paper we present the foundations of RAPIDS ("Replicated Ada Partitions In Distributed Systems"), an implementation of the PCS supporting the transparent replication of partitions in distributed Ada 95 using semi-active replication. The inherently non-deterministic executions of multi-tasked partitions are modeled as piecewise deterministic histories. I discuss the validity and correctness of this model of computation and show how it can be used for efficient semi-active replication. The R
APIDS
prototype ensures that replicas of a partition all go through the same history and are hence consistent.
Prioritizing remote procedure calls in Ada distributed systems
Authors: Gutiérrez García J. J. , González Harbour M.
Published: October 2004

In this paper we discuss the assignment of priorities to the execution of remote procedure calls in distributed real-time systems that are programmed using the Distributed Systems Annex (DSA) of Ada 95. We first discuss the current priority model used in the Glade implementation of the DSA. We then present some theoretical results that show that a more flexible priority assignment methodology can provide much better schedulable utilization levels. Based upon these results we propose an implementation that would allow using this priority assignment methodology in Glade. Finally, we propose new features for a future DSA that would allow prioritizing remote procedure calls in a flexible manner.
Real-time programming with GNAT
Authors: de la Puente Juan A. , Ruiz José F. , González-Barahona Jesús M.
Published: October 2004

The fact that most of the GNAT ports are based on non real-time operating systems leads to a reduced usability for developing real-time systems. Otherwise, existing ports over real-time operating systems are excessively complex, since GNAT uses only a reduced set of their functionality, and with a very specific semantic. This paper describes the implementation of a low-level tasking support for the GNAT run-time. In order to achieve a predictable real-time behaviour we have developed a very simple library, built to fit only the GNAT tasking requirements. We have also designed a bare machine kernel which provides the minimum environment needed by the upper layers.
A comparative case study of three database application development environments
Authors: Ahmed Iftikhar , Lochovsky Frederick H.
Published: October 2004

This paper describes an exploratory case study that investigates the claim that the object-oriented approach to information systems development reduces development effort and improves maintainability. Software metrics for development effort, complexity, and maintainability of three functionally similar 4GL database development environments, one objected-oriented and two traditional (relational) are compared. The results indicate that programs developed using the object-oriented environment needed fewer lines of code, had less volume, required less effort, were less complex and were more maintainable than those developed using the traditional 4GL environments.
Add finalization
Authors: Grein Christoph
Published: October 2004

With its tagged types and appropriate dynamic binding facilities, Ada95 has become a mighty language. Virtually ad libidum, you can add new components to given types of a class. This seems to imply some kind of arbitrariness in the choice of the starting point of a type hierarchy (the root of a class). However, this arbitrariness is only a seeming one and you rather have to exercise utmost care in choosing the root lest you might run into troubles at the end. This fact is highlighted by the following problem about controlled types I found some time ago in the Ada internet forum Chat@Gnat.com, which I thought might be of common interest.
Ada
Authors: Wood Dave
Published: October 2004

This paper provides a brief summary of a presentation provided at the 1998 SIGAda conference in Washington DC. Part of the "Commercializing Ada" workshop, the presentation discusses the alleged commercial failure of Ada, and how we can improve Ada's commercial lot in life.
The Ravenscar Profile
Authors: Burns Alan
Published: October 2004

The Ravenscar profile is described. All its features and restrictions are noted. Also, the means of designating the profile is presented. Detailed motivations for the profile are not given. The aim of the paper is to summarize the outcome of deliberations at the 8th and 9th International Workshops on Real-Time Ada Issues.
A multi-disciplinary framework for the management of interorganizational systems
Authors: Kumar Ram L. , Crook Connie W.
Published: October 2004

Interorganizational information systems (IOS) are information technology (IT)-based systems that link multiple organizations. Management of these systems could be significantly more complex than managing IT within individual organizations. We explore the complexities of managing IOS using case studies and propose a multidisciplinary framework that includes collaboration, organization, and technology issues for the design and management of such organizations. Multiple case studies are presented to illustrate the proposed framework. Managerial and research implications are also discussed.
Exploring the boundaries of successful GSS application
Authors: de Vreede Gert-Jan , de Bruijn Hans
Published: October 2004

Technologies used to support group work are based on, and contain underlying assumptions regarding, how people work together. The appropriateness of such assumptions is an important factor in determining the successful employment of the technology. This paper uses an action research approach to explore the boundaries of effective GSS application by challenging the basic assumptions built into GSS. This exploration is carried out in the context of a particular arena in which groups have to interact to reach a certain goal: inter-organizational policy networks. From nine cases it appears that GSS are most effective in the orientation phase of inter-organizational policy making, while GSS should be avoided during the separation phase where winners and losers can be identified. During the package deal phase of an inter-organizational policy making process, GSS may have added value to offer, but the technology should be employed with caution. These findings are consistent with various experimental studies that found that GSS application is more successful for creativity tasks than for preference tasks and mixed motive tasks.
Appropriations and patterns in the use of group support systems
Authors: Chudoba Katherine M.
Published: October 2004

This paper describes a macro-level coding scheme to distinguish patterns that occur in groups using a group support system (GSS). The coding scheme has roots in adaptive structuration theory (AST) with its emphasis on how technology is appropriated or used, and discourse analysis that requires one consider the context of the larger discussion when analyzing textual data. The macro-level coding scheme revolves around junctures that occur during group meetings such as when a group either chooses to use the GSS software or chooses to accomplish some aspect of the task without the software. After identifying a juncture, a brief description is written detailing how group members responded to the opportunity presented by the juncture. Qualitative analysis is then used to identify patterns in how the technology is used. Application of the coding scheme is demonstrated with data gathered from 17 groups that met three times over a two-week period.
Towards a secure platform for distributed mobile object computing
Authors: Lacoste Marc
Published: October 2004

We present some issues relevant to the design of a secure platform for distributed mobile computing, that goes beyond existing ad-hoc approaches to software mobility. This platform aims to support wide-area computing applications such as active network infrastructures or network supervision tools. Our contribution is two-fold: the first part of the paper is a survey of the security features of a few languages and virtual machines as regards authentication, access control, and communications security. We then discuss a possible architecture for a secure virtual machine for distributed mobile computing based on interesting features found in the implementations studied.
Scalable scheduling on a network of workstations
Authors: Lu Sanglu , Xie Li
Published: October 2004

This paper presents an adaptive scalable scheduling model ASCS based on NOWs, which provides a dynamic load sharing facility by allowing tasks to scale up to utilize desired excess computing capacity depending upon available workstations on a NOW, and also scale down to maintain workstation autonomy. In this paper, a hierarchical scheduling policy is described: the inter-cluster scheduling provides a simple, fast and less-overhead load sharing among clusters in the system; and the intra-cluster scheduling provides a high performance scheduling in a cluster, and an adaptive coscheduling is implemented, some scalable algorithms are introduced to schedule those parallel/distributed applications to adapt to system changes. The simulation results show that the ASCS Model has better performance with less overhead, and it can well adapt to different system structures, and also well adapt to large scale systems.
pgmcc
Authors: Rizzo Luigi
Published: October 2004

We present a single rate multicast congestion control scheme
(pgmcc) which is TCP-friendly and achieves scalability, stability and fast response to variations in network conditions. pgmcc is suitable for both non-reliable and reliable data transfers; it uses a window-based TCP-like controller based on positive ACKs and run between the sender and a group's representative, the
acker
. The innovative part of pgmcc is a fast and low-overhead procedure to select (and track changes of) the acker, which permits us to consider the acker as a
moving
receiver rather than a
changing
one. As such, the scheme is robust to measurement errors, and supports fast response to changes in the receiver set and/or network conditions. The scheme has been implemented in the PGM protocol, and the paper presents a number of experimental results on its performance.
Fault isolation in multicast trees
Authors: Reddy Anoop , Govindan Ramesh , Estrin Deborah
Published: October 2004

Fault isolation has received little attention in the Internet research literature. We take a step towards addressing this deficiency, exploring robust and scalable techniques by which multicast receivers can (in some cases, approximately) locate the on-tree router responsible for a route change, or the link responsible for significant packet loss. A common property of our techniques is that receivers with overlapped paths coordinate to share the responsibility of monitoring paths to the source. Our techniques assume no additional path monitoring capability other than that provided by
multicast traceroute
(mtrace).
The content and access dynamics of a busy Web site
Authors: Padmanabhan Venkata N. , Qiu Lili
Published: October 2004

In this paper, we study the dynamics of the MSNBC news site, one of the busiest Web sites in the Internet today. Unlike many other efforts that have analyzed client accesses as seen by proxies, we focus on the server end. We analyze the dynamics of both the server content and client accesses made to the server. The former considers the content creation and modification process while the latter considers page popularity and locality in client accesses. Some of our key results are: (a) files tend to change little when they are modified, (b) a small set of files tends to get modified repeatedly, (c) file popularity follows a Zipf-like distribution with a parameter &agr that is much larger than reported in previous, proxy-based studies, and (d) there is significant temporal stability in file popularity but not much stability in the domains from which clients access the popular content. We discuss the implications of these findings for techniques such as Web caching (including cache consistency algorithms), and prefetching or server-based ``push'' of Web content.
Tuning RED for Web traffic
Authors: Christiansen Mikkel , Jeffay Kevin , Ott David , Smith F. Donelson
Published: October 2004

We study the effects of RED on the performance of Web browsing with a novel aspect of our work being the use of a user-centric measure of performance - response time for HTTP request-response pairs. We empirically evaluate RED across a range of parameter settings and offered loads. Our results show that: (1) contrary to expectations, compared to a FIFO queue, RED has a minimal effect on HTTP response times for offered loads up to 90% of link ca?pacity, (2) response times at loads in this range are not substantially effected by RED pa?rameters, (3) between 90% and 100% load, RED can be carefully tuned to yield performance somewhat superior to FIFO, however, response times are quite sensitive to the actual RED pa?rameter values selected, and (4) in such heavily congested networks, RED parameters that provide the best link utilization produce poorer response times. We conclude that for links carrying only web traf?fic, RED queue management appears to provide no clear advantage over tail-drop FIFO for end-user response times.
Implementation of state machines with tasks and protected objects
Authors: Sandén Bo I.
Published: October 2004

State machines are common in real-time software. They are also a standard way of describing the life of an object in object-oriented analysis and design. Their use is fairly straightforward but non-trivial. The examples in this article show implementations of state machines and associated activities by means of tasks and protected objects. They cover a range of synchronization and communication needs between activity and state machine.
A moment of perfect clarity I
Authors: Hemaspaandra Lane A. , Glaßer Christian
Published: October 2004

We discuss the history and uses of the parallel census technique---an elegant tool in the study of certain computational objects having polynomially bounded census functions. A sequel [GH] will discuss advances (including [CNS95] and Glaßer [Gla00]), some related to the parallel census technique and some due to other approaches, in the complexity-class collapses that follow if NP has sparse hard sets under reductions weaker than (full) truth-table reductions.
Controlling dynamic objects in large Ada systems
Authors: Rosen Steven M.
Published: October 2004

This paper describes a generalized technique for controlling the growth of dynamically allocated objects within an Ada system due to the careless, yet innocent misuse of access types, allocators and instantiations of the generic procedure
UNCHECKED_DEALLOCATION
. The technique outlined here involves reliance on Ada's strong typing model and in particular, the judicious use of
limited private
data types in conjunction with generic packages and data abstraction facilities.
Proposal for adding discriminants for Ada task types
Authors: Clarson Donald R.
Published: October 2004

This paper proposes an addition to the Ada Programming Language which will allow a set of values to be passed as discriminant values when a task object is created. This feature will be useful to avoid an additional task entry call following task activation for some applications. Syntax and semantic rules are presented together with several contexts where the feature may be used.
Hardware architectures for programming languages and programming languages for hardware architectures
Authors: Wirth Niklaus
Published: October 2004

Programming Languages and Operating Systems introduce abstractions which allow the programmer to ignore details of an implementation. Support of an abstraction must not only concentrate on promoting the efficiency of an implementation, but also on providing the necessary guards against violations of the abstractions. In the frantic drive for efficiency the second goal has been neglected. There are indications that recent designs which are claimed to be both simple and powerful, achieve efficiency by shifting the complex issues of code generation and of appropriate guards onto compilers.Complexity has become the common hallmark of software as well as hardware designs. It cannot be mastered by the common practices of testing and simulation. Hardware design may profit from developments in programming methodology by adopting proof techniques similar to those used in programming.
Tags and type checking in LISP: hardware and software approaches
Authors: Steenkiste Peter , Hennessy John
Published: October 2004

One of the major factors that distinguishes LISP from many other languages (Pascal, C, Fortran, etc.) is the need for run-time type checking. Run-time type checking is implemented by adding to each data object a tag that encodes type information. Tags must be compared for type compatibility, removed when using the data, and inserted when new data items are created. This tag manipulation, together with other work related to dynamic type checking and generic operations, constitutes a significant component of the execution time of LISP programs. This has led both to the development of LISP machines that support tag checking in hardware and to the avoidance of type checking by users running on stock hardware. To understand the role and necessity of special-purpose hardware for tag handling, we first measure the cost of type checking operations for a group of LISP programs. We then examine hardware and software implementations of tag operations and estimate the cost of tag handling with the different tag implementation schemes. The data shows that minimal levels of support provide most of the benefits, and that tag operations can be relatively inexpensive, even when no special hardware support is present.
Cheap hardware support for software debugging and profiling
Authors: Cargill T. A. , Locanthi B. N.
Published: October 2004

We wish to determine the effectiveness of some simple hardware for debugging and profiling compiled programs on a conventional processor. The hardware cost is small -- a counter decremented on each instruction that raises an exception when its value becomes zero. With the counter a debugger can provide data watchpoints and reverse execution: a profiler can measure the total instruction cost of a code segment and sample the program counter accurately. Such a counter has been included on a single-board MC68020 workstation, for which system software is currently being written. We will report our progress at the symposium.
Integer multiplication and division on the HP precision architecture
Authors: Magenheimer Daniel J. , Peters Liz , Pettis Karl , Zuras Dan
Published: October 2004

In recent years, many architectural design efforts have focused on maximizing performance for frequently executed, simple instructions. Although these efforts have resulted in machines with better average price/performance ratios, certain complex instructions and, thus, certain classes of programs which heavily depend on these instructions may suffer by comparison. Integer multiplication and division are one such set of complex instructions. This paper describes how a small set of primitive instructions combined with careful frequency analysis and clever programming allows the Hewlett-Packard Precision Architecture integer multiplication and division implementation to provide adequate performance at little or no hardware cost.
How many addressing modes are enough?
Authors: Chow F. , Correll S. , Himelstein M. , Killian E. , Weber L.
Published: October 2004

Programs naturally require a variety of memory-addressing modes. It isn't necessary to provide them in hardware, however, if a compiler can synthesize them from a few primitive modes. This not only simplifies the hardware, but also permits the compiler to use its understanding of the program to economize on the modes which it uses. We present some compilation techniques that allow the compiler to deal effectively with a single addressing mode in a target RISC processor. We also give measurements to show the benefits of such techniques, and to support our assertion that a single addressing mode is adequate for a general purpose processor, provided that mode incorporates both a pointer and an offset.
The ZS-1 central processor
Authors: Smith J. E. , Dermer G. E. , Vanderwarn B. D. , Klinger S. D. , Rozewski C. M. , Fowler D. L. , Scidmore K. R. , Laudon J. P.
Published: October 2004

The Astronautics ZS-1 is a high speed, 64-bit computer system designed for scientific and engineering applications. The ZS-1 central processor uses a decoupled architecture, which splits instructions into two streams---one for fixed point/memory address computation and the other for floating point operations. The two instruction streams are then processed in parallel. Pipelining is also used extensively throughout the ZS-1.This paper describes the architecture and implementation of the ZS-1 central processor, beginning with some of the basic design objectives. Descriptions of the instruction set, pipeline structure, and virtual memory implementation demonstrate the methods used to satisfy the objectives. High performance is achieved through a combination of static (compile-time) instruction scheduling and dynamic (run-time) scheduling. Both types of scheduling are illustrated with examples.
Software engineering education
Authors: McCormick John W.
Published: October 2004

An introductory undergraduate course in real-time embedded software development should acquaint students with the fundamental scientific issues of real-time computing and practical skills in software development. While the theoretical issues can be covered without a laboratory, real-time embedded programming skills require the experiences that a laboratory provides. A major problem is finding equipment suitable for teaching these skills. For over a decade I have used a computer controlled model railroad in my real-time embedded systems course
Efficient implementation of the OSI transport protocol checksum algorithm using 8/16-bit arithmetic
Authors: Cockburn A.
Published: October 2004

The checksum algorithm recommended in the OSI transport-protocol specfications is an arithemetic checksum algorithm which makes heavy use of base-255 addition. In this technical note, an efficient implementation of the recommended checksum algorithm is derived, using 8-bit unsigned addition as the base for an inexpensive modulo-255 addition.
A successful example of a layered-architecture based embedded development with Ada 83 for standard-missile control
Authors: Spicer Kelly L.
Published: October 2004

A need for a standard understandable software architecture that can be reused from project to project has long been recognized. This paper describes the software architecture used for the Standard-Missile-3 (SM-3), Stage-3 development program. The architecture was defined based on hierarchical principles with the goal of providing a general solution for the architecture-level design for embedded systems. An architecture-need statement is first presented listing the attributes of the needed architecture. An overview of the notation is given, and then the layered architecture is described. How the architecture supports multi-build projects is then described. A brief discussion on reuse is then provided --- both reuse of algorithms in the architecture and reuse of the architecture itself. The paper concludes with a few comments on support for the software process. The paper includes two attachments: Attachment A - a list of acronyms and other definitions, and Attachment B - an overview of the SM-3 Stage-3 software requirements.
The SPARK way to correctness is via abstraction
Authors: Barnes John
Published: October 2004

This paper gives a short introduction to the S
PARK
language and illustrates how the use of abstraction leads towards correctness.
A moment of perfect clarity II
Authors: Glaßer Christian , Hemaspaandra Lane A.
Published: October 2004

This issue's column, Part II of the article started in the preceding issue, is about progress on the question of whether NP has sparse hard sets with respect to weak reductions.Upcoming Complexity Theory Column articles include A. Werschulz on information-based complexity; J. Castro, R. Gavaldà, and D. Guijarro on what complexity theorists can learn from learning theory; S. Ravi Kumar and D. Sivakumar on a to-be-announced topic; M. Holzer and P. McKenzie on alternating stack machines; and R. Paturi on the complexity of
k
-SAT.
Review of Parameterized Complexity by R. Downey and M. Fellows
Authors: Istrate Gabriel
Published: October 2004

One of the most pervasive critiques of Computational Complexity, coming from the applied Computer Science community, is that it is an abstract, largely irrelevant field, that fails to capture the various intuitions concerning the complexity of "real-world" instances they have gathered through experiments. One aspect of these intuitions is that while most problems of practical interest tend to be intractable from a standard complexity-theoretic point of view, in many cases such problems have natural "structural" parameters, and practically relevant instances are often associated with "small" values of these parameters.Parameterized Complexity is an extension of Complexity Theory that attempts to formalize and deal with this intuition. It has already been applied to fields such as Databases, Logic and Constraint Programming, Computational Biology, Nonmonotonic Reasoning, Natural Language Processing, Cognitive Science, and Robotics. Some of its ideas have even been discovered independently by practitioners working in these areas. We do not attempt a further presentation (the interested reader can consult two excellent surveys [DF99, DFS99]), but want to illustrate this point through a revealing example: it has long been known that the register-allocation problem for imperative programming language amounts to a coloring problem on the associated control-flow graph, thus it seems, at a first glance, hard even in an approximate sense. On the other hand Thorup [Th98] has shown that such graphs are characterized by a bounded value (at most 10) of an intrinsic parameter called
treewidth,
that guarantees the existence of an approximation algorithm with substantially better performance than the one available for general graphs.The present book is an attempt to a first presentation of this emerging area by two of its most active proponents.
Efficient and practical DHEKE protocols
Authors: Lin Chun-Li , Sun Hung-Min , Hwang Tzonelih
Published: October 2004

In 1992, Bellovin and Merritt proposed
Encrypted Key Exchange
(EKE) protocols for preventing dictionary attacks on weak chosen passwords. In 1995, Steiner, Tsudik, and Waidner proposed a minimal DHEKE protocol which simplified the Diffie-Hellman based one of Bellovin and Merritts' protocols. In this paper, we propose two improvements on the minimal DHEKE protocol. These two improvements can reduce the computational cost further.
Extending Ada's real-time systems annex with the POSIX scheduling services
Authors: Rivas Mario Aldea , Harbour Michael González
Published: October 2004

In this paper we propose extending the scheduling model of the Ada 95 Real-Time Systems Annex with the services specified in the Real-Time POSIX standard. These services include a round robin within priorities scheduling policy, a sporadic server scheduling policy, and execution time clocks and timers. With these services the Ada Real-Time Annex will enable addressing a larger number of application requirements.
The Ravenscar profile for high-integrity Java programs?
Authors: Dobbing Brian
Published: October 2004

The Ravenscar Profile was a major output of the 8
th
International Real-Time Ada Workshop. The profile defines a subset of the Ada95 tasking constructs that matches the requirements of Safety Critical, High Integrity and Hard Real-Time systems by eliminating constructs with high overhead or non-deterministic behavior (semantically or temporally) whilst retaining those elements that form the basic building blocks for constructing analyzable real-time systems.The recent explosion in interest and use of the Java™ platform for embedded devices has exposed basic flaws in the semantics of its real-time constructs, and this has led to initiatives to extend the language to address these weaknesses. Key personnel involved in the definition of the Real-Time Annex for Ada95 and the Ravenscar Profile also influenced the design of the real-time extensions to Java™, and so it is not surprising that these extensions follow closely the experiences learned from Ada.This paper describes the proposed set of extensions to Java™ to support real-time and high integrity systems, drawing parallels with the Ravenscar Profile definition. It suggests the possibility of co-existence and interoperability of Ravenscar-compliant Ada and RT-Java partitions within a high integrity or safety critical system.
Towards a real-time distributed systems annex in Ada
Authors: Guitiérrez García José Javier , Harbour Michael González
Published: October 2004

In this paper we address the problem of combining two issues that are standardized separately in two Ada 95 annexes: Real-Time Systems (Annex D) and Distributed Systems (Annex E). With these annexes it is possible to build applications with real-time requirements, or alternatively distributed applications; but real-time distributed applications are not directly supported. In this paper we propose extensions to the Distributed Systems Annex that would provide support for developing distributed real-time applications in Ada. The paper proposes an interface for assigning priorities to the messages in the interconnection networks, and also to the tasks executing remote operations, in a way that avoids priority inversions. It also addresses the issues of configuration of the RPC handler tasks and non blocking asynchronous remote procedure calls.
Combining tasking and transactions, part II
Authors: Kienzle Jörg , Romanovsky Alexander
Published: October 2004

This position paper is a follow-up paper of [1], presented at the last IRTAW workshop. The paper describes a model for providing transaction support for concurrent programming languages such as Ada 95. In order to achieve smooth integration, the use of the concurrency features provided by the Ada language should not be restricted inside a transaction. A transaction model that meets this requirement is presented. Tasks inside such a transaction may spawn new tasks, but also external tasks are allowed to join an ongoing transaction. A blocking commit protocol ensures that no task leaves the transaction before its outcome has been determined. Exceptions are used to inform all participants in case a transaction aborts. Possible interfaces for the Ada programmer are discussed.