bluuebunny/crossref_metadata_2025 huggingface dataset:
Computational geometry column 36
Authors: O'Rourke Joseph
Published: October 2004

Two results in "computational origami" are illustrated.
Digest of proceedings seventh IEEE workshop on hot topics in operating systems March 29-30 1999, Rio Rico, AZ
Authors: Satyanarayanan M.
Published: October 2004

The Seventh IEEE Workshop on Hot Topics in Operating Systems was held on March 29-30 1999 at the Rio Rico Resort & Country Club, south of Tucson, Arizona. The General Chair, Peter Druschel, and the Local Arrangements Chair, John Hartman, had gone to considerable effort to make the operation of the workshop smooth and pleasant for the participants. The secluded desert locale, the effect of brilliant sunshine and blue skies on winter-jaded northerners, and the enthusiasm and energy of the participants all combined to offer an ideal setting for two days of technical exchange and out-of-the-box thinking. A variety of outdoor activities awaited participants who arrived early, and a kickoff reception on Sunday evening enabled participants to get to know each other before the technical meetings began.What follows is a summary of the discussions that took place during the workshop. It is meant to be a supplement, not a substitute, for the papers in the proceedings. Rather than producing a verbatim transcript, I've tried to focus on those interactions that seemed most insightful, controversial or evoked most response from the audience. Any such report must, by its very nature, be subjective. I've tried hard to be objective, but I'm sure that are some places where my personal biases show through. My apologies in advance if you attended the workshop and your favorite comment, question or discussion isn't mentioned here. This material is based on detailed notes taken by four student volunteers (Gretta Bartels, Buck Krasic, Rajeev Balasubramonian, and Ben Fleis). They did an excellent job of taking detailed and complete notes: any errors or omissions in this digest are my responsibility, not theirs.
Security issues in ATM networks
Authors: Patiyoot Danai , Shepard S. J.
Published: October 2004

This paper presents a survey of existing solutions aiming to secure communications over ATM network. Details are given about: the security services offered, their placement within ATM protocol reference model, the mechanism to negotiate security services, techniques to provides synchronisation and key exchange protocol. Additionally, this paper proposes a new ATM security solution.
WASS
Authors: Patiyoot D. , Shepherd S. J.
Published: October 2004

Recent years have witnessed the rapid growth in demanding for the use of wireless networks especially the one with can transmit all the service. Wireless ATM is the one that fulfil those requirements. This paper looks at the security issues in wireless ATM networks. It proposes the security services into user and control plane.
A nested mutual authentication protocol
Authors: Bull John A. , Otway David J.
Published: October 2004

This paper describes an authentication protocol that is suited to modern, object-based, client-server systems. Each object in a chain, whether acting in a client or server role, handles authentication with its neighbours, without any need to be aware of the resultant global behaviour. Session keys are returned by an authentication server which services a client-server chain as a whole: nested requests are built along the forward chain; the final server presents the whole package to the authentication server; and sessions keys are delivered back down the chain. The protocol, as described, avoids entanglement with the politics of cryptography by using One-Way-Hash-Functions throughout. The authentication chain might traverse different legal jurisdictions, but adjacent applications can use returned session keys for any legitimate purpose, including message sealing or encryption.
Resource partitioning in general purpose operating systems
Authors: Waddington D. G. , Hutchison D.
Published: October 2004

The principal role of the operating system is that of resource management. Its task is to present a set of appropriate services to the applications and users it supports. Traditionally, general-purpose operating systems, including Windows NT, federate resource sharing in a fair manner, with the predominant goal of efficient resource utilisation. As a result the chosen scheduling algorithms are not suited to applications that have stringent Quality-of-Service (QoS) and resource management requirements, such as continuous media streaming applications. Several approaches to resource management that are able to meet these requirements, including the use of deterministic schedulers, are well established. Operating systems already exist that provide services for fine-grained resource partitioning and QoS based allocations. Nevertheless, the question arises: can we introduce suitable management mechanisms into general-purpose operating systems that will provide adequate support for the majority of resource sensitive applications, particularly multimedia? Or are there inherent problems in general-purpose operating system architectures that demand significant re-engineering?We attempt to answer this question by proposing the Protected Virtual Machine (PVM) architecture. This introduces mechanisms into Windows NT that enable partitioning of resources and protection from resource interference. The functionality of the PVM architecture is two-fold. First it introduces the necessary scheduling mechanisms and atomic resource abstractions into the operating system, and second it provides a higher level reservation and admission service directly to applications. The resulting system is able to provide both a best-effort service for applications with less stringent needs and a guaranteed service for multimedia and other resource critical processing in a shared environment, By enhancing the existing operating system, legacy applications can still be supported, thus avoiding a prominent obstacle in existing real-time and multimedia operating systems.
Dynamic ceiling priorities and Ada 95
Authors: Real Jorge , Wellings Andy
Published: October 2004

Ada 95 provides dynamic priorities for tasks but ceiling priorities for protected objects are statically assigned by means of a pragma. The semantic complexity as well as the potential inefficiency of any resulting implementation seem to have been the main objections to including dynamic ceilings in Ada 95. Nevertheless, in frequent scenarios such as multi-moded real-time systems, it is desirable for ceiling priorities to be dynamic, to accommodate the different priority assignments given to tasks in the different modes. This problem is usually worked around by applying the so-called ceiling of ceilings as a static ceiling for all modes, which may result in lower schedulability as extra blocking potentially occurs. In this paper we investigate on how to use a hypothetical
Set_Ceiling
dynamic operation, without incurring the risk of semantic ambiguities, and how a multi-moded system can benefit from its existence.
Combining tasking and transaction
Authors: Kienzle Jörg
Published: October 2004

This position paper discusses the issues in design and development of a transaction support for Ada 95. Transactions and other fault tolerance mechanisms are reviewed, and their applicability in a concurrent programming language is analyzed. Possible ways of integration are presented, and implementation problems are discussed.
SimpleGraphics
Authors: Moody Scott Arthur , Kwok Samuel , Karr Dale
Published: October 2004

Visualization of complex software applications is an exciting and challenging field. Useful displays are invaluable for developers in analysis of their software systems, and for meaningful system presentations to customers at a higher conceptual level.There have been many notable visualization examples applicable to data centric systems, including the GRASP code visualizer[11], the UW Illustrating Compiler[14], and the Information Space Visualizations embodied in Cone Trees[7] and Data Walls[8]. As conceptual and abstraction levels of these advanced graphics increases and becomes more prevalent, and as the real-world applications become more complicated from concurrency and distribution, the interfacing cohesion process becomes more difficult.This paper describes concepts and issues for integrating visualization techniques into multi-threaded and distributed applications, and shows foundation use available across application domains.
SimpleGraphics
is a term used in this paper to describe these powerful and rapidly developed visualizations applied to soft real-time applications. For the applications described here to meet the "simple" criteria they must be both conceptually simple and quickly developed - in say under 10 minutes. This leads to their use when appropriate in a "what if" manner, as well as taking them out if no longer needed. Looking ahead, the newer embedded devices, such as the
AutoPC
or the
PalmPilot,
have a small graphic foot print and will probably not allow for complicated graphics, leading to more use of abstractions like
SimpleGraphics.
Newer object oriented concurrency and distribution abstractions are being explored and applied to augment the work since the last International Real-Time Ada Workshop (IRTAW)[6][5]. With pervasive concurrent and distributed systems under development, it becomes clear that better controls and visualizations techniques are necessary, and Ada provides elegant solution techniques that can evolve with changing requirements. The graphic language, Tcl/Tk[9], is used here both for it's portability and its higher abstraction (through less syntax) supporting rapid development feedback.The benefits and impacts from this work include highlighting multi-threaded real-time issues, showing rapid turnaround through reuse, robust development through objects, better visualization techniques, and techniques for interfacing to other languages. In short, the goals of the 9th IRTAW are addressed in various aspects within this body of work.
How to verify concurrent Ada programs
Authors: Burns A. , Wellings A. J.
Published: October 2004

Ada 95 is an expressive concurrent programming language with which it is possible to build complex multi-tasking applications. Much of the complexity of these applications stem from the interactions between the tasks. This paper argues that model checking tools are now mature enough that they can be used by engineers to verify the logical correctness of their tasking algorithms. The paper illustrates the approach by showing the correctness of an Ada implementation of the atomic action protocol.
A Linux kernel module implementation of restricted Ada tasking
Authors: Shen Hongfeng , Baker Theodore P.
Published: October 2004

An Ada tasking kernel is implemented as a layer beneath the Linux operating system on a PC-compatible machine. This implementation is derived from Yodaiken's Real-Time Linux kernel, with new scheduling and synchronization primitives introduced specifically to support the GNAT Ada runtime system. Primitive operations for real-time Ada tasks are directly implemented on top of the underlying hardware in the form of a loadable Linux kernel module. This design not only reduces execution overhead and improves control over execution timing for tasks, but also opens the door for a simple restricted-tasking runtime system that could be certified for safety-critical applications.
The DataIndex
Authors: Datta Anindya , Viguier Igor
Published: October 2004

In this paper we present DataIndexes, a family of design strategies for data warehouses to support OnLine Analytical Processing (OLAP). As the name implies, DataIndexes are both a storage structure for the warehoused relational data and an indexing scheme to provide fast access to that data. We present two simple DataIndexes: the Basic DataIndex (BDI), which can be used for any attribute and the Join DataIndex (JDI), which is used for foreign-key attributes. Either structure can be shown to significantly improve query response times in most cases. And, since they serve as indexes as well as the store of base data, DataIndexes actually define a physical design strategy for a data warehouse where the indexing, for all intents and purposes, comes for "free."
Reconciling top-down and bottom-up design approaches in RMM
Authors: Isakowitz Tomás , Kamis Arnold , Koufaris Marios
Published: October 2004

The proliferation of intranets and extranets as well as the vast expansion of the World Wide Web (WWW) and electronic commerce indicate the need for a structured hypermedia design methodology that will guide the design, development, and maintenance of large multimedia and hypermedia information systems and collaborative systems. The Relationship Management Methodology (RMM) is a well-known hypermedia design methodology. In this paper we provide an extension to it that enhances the design process. We present an iterative process of application design that incorporates the design of the entire application as well as its components. The process includes the design of an application diagram in a top-down fashion, the design of the components or building blocks using the construct of an m-slice, and the regeneration of the application diagram in a bottom-up fashion. An iterative comparison and refinement of the two versions of the application diagram ensure a better final application.
Converting an Ada 83 application to Ada 95
Authors: Cole Oliver
Published: October 2004

This paper can also be found at the OC Systems web site.
Ada as a teaching language
Authors: Wong SY
Published: October 2004

There is a need for a single, simple language suitable both for teaching the important fundamentals of programming and for practical applications long after graduation.
An industry analysis of developer beliefs about object-oriented systems development
Authors: Johnson Richard A. , Hardgrave Bill C. , Doke E. Reed
Published: October 2004

Object-oriented systems development (OOSD) is a recent innovation in software development that is often cited as a viable solution to many of the ills plaguing this critical industry. However, some express doubt about the potentially over-hyped claims of OOSD. While there are many accounts of the successful application of OOSD, widespread acceptance has not been achieved, implying that OOSD may not be viewed as positively by industry as the literature would suggest.To address this dilemma, the present study examines a wide variety of specific beliefs about OOSD as provided by a survey of 150 systems developers. Using Ajzen's (1988) theory of planned behavior as a foundation, an exploratory factor analysis is performed to determine which specific beliefs about OOSD are indeed salient indicators of three fundamental concepts that should influence acceptance: the usefulness of OOSD, social pressure to use OOSD, and the ease of using OOSD. The results of the study reveal that while many specific beliefs about OOSD are indeed salient indicators of these more fundamental, potentially influential factors, many other beliefs are not. This study should prove helpful to practitioners who are considering the adoption or continued use of OOSD, and to researchers who are interested in the diffusion of innovations in general
IS “maintainability”
Authors: Swanson E. Burton
Published: October 2004

This paper reexamines information system (IS)
maintainability
and takes a new and inclusive view of it and its effects. It proposes that an IS is maintainable to the extent that its maintenance, operation, and use is economical in its use of resources. A model is offered which puts IS maintainability in the larger developmental context and suggests a number of related propositions. To the question of whether increased maintainability should reduce an organization's maintenance effort, a straightforward analysis leads to what, for some, may be a surprising answer. Where IS maintainability is enhanced, organizations can sometimes be better off by sustaining, not decreasing, their overall maintenance efforts.
Groupware comes to the Internet
Authors: Wheeler Bradley C. , Dennis Alan R. , Press Laurence I.
Published: October 2004

Early experiences with Web-based groupware point to new collaboration opportunities within and between organizations. We report the results of a study of more than 100 organizations that have used Web-based groupware to understand better how they are using it and what advantages and disadvantages they have experienced. We then use these data to develop a framework for analyzing and assessing the fit of groupware systems to organizational needs. We close with a discussion of the evolution and future of groupware.
Measuring disagreement in groups facing limited-choice problems
Authors: Whitworth Brian , Felton Roy
Published: October 2004

Agreement is an important concept in group interaction, both for computer-mediated and face-to-face groups. This paper presents a measure of disagreement,

D,

for groups facing limited-choice problems, based on the average pair-wise separations between group member responses. It allows a meaningful disagreement value to be assigned to any group response pattern. The same logic also provides an individual level measure,

d,

giving the disagreement of individuals within the group.The properties of this measure are explored and found to be similar to those expected of a measure of disagreement. For nominal data, such as produced by questionnaire responses,

D

offers a standard scale of disagreement from 0 to 1 for any size group facing any number of mutually exclusive choices. The measures can be inverted to show agreement, although this does not necessarily predict group coalescence, as polarized groups can also contain considerable agreement.The measure can be extended to ranked, interval, and ratio-scale solution choices. In this case,

D

is equal to twice the variance of the solution scores. The existence of an equivalent measure of ecological diversity further suggests the possibility of a generalized concept of dispersion. An example application is given, illustrating how disagreement at both the individual and group levels can be meaningfully and usefully represented by

d

and

D.
Establishing a foundation for collaborative scenario elicitation
Authors: Hickey Ann M. , Dean Douglas L. , Nunamaker Jay F.
Published: October 2004

Eliciting and integrating requirements from large groups of diverse users remains a major challenge for the software engineering community. Scenarios are becoming recognized as valuable means of identifying actions taken by users when executing a business process and interacting with an information system, and therefore have great potential for addressing requirements elicitation problems. A review of the scenario literature indicates that, although there is widespread agreement on the usefulness of scenarios, there are many unanswered questions about how to elicit scenario definitions from individual users and user groups efficiently.This research examines how increasing the structure of scenario definitions affects scenario quality and the efficiency of scenario definition by individual users. During a laboratory experiment, subjects defined scenarios using a general-purpose GSS, GroupSystems Group Outliner, with one of three textual scenario formats that ranged from unstructured to very structured. Scenario quality and the efficiency of scenario definition by users were compared across the formats. Results highlighted the efficiency of the unstructured format but revealed that all formats produced incomplete scenario definitions. Recommendations are made for an iterative collaborative scenario process and a special-purpose GSS scenario tool that may overcome some of these problems.
Equation-based congestion control for unicast applications
Authors: Floyd Sally , Handley Mark , Padhye Jitendra , Widmer Jörg
Published: October 2004

This paper proposes a mechanism for equation-based congestion control for unicast traffic. Most best-effort traffic in the current Internet is well-served by the dominant transport protocol, TCP. However, traffic such as best-effort unicast streaming multimedia could find use for a TCP-friendly congestion control mechanism that refrains from reducing the sending rate in half in response to a single packet drop. With our mechanism, the sender explicitly adjusts its sending rate as a function of the measured rate of loss events, where a
loss event
consists of one or more packets dropped within a single round-trip time. We use both simulations and experiments over the Internet to explore performance.
Decoupling QoS control from core routers
Authors: Zhang Zhi-Li , Duan Zhenhai , Gao Lixin , Hou Yiwei Thomas
Published: October 2004

For scalable support of guaranteed services that decouples the QoS control plane from the packet forwarding plane. More specifically, under this architecture,
core routers do not maintain any QoS reservation states, whether per-flow or aggregate
. Instead, QoS reservation states are stored at and managed by bandwidth broker(s). There are several advantages of such a bandwidth broker architecture. Among others, it relieves core routers of QoS control functions such as admission control and QoS state management, and thus enables a network service provider to introduce new (guaranteed) services without necessarily requiring software/hardware upgrades at core routers. Furthermore, it allows us to design efficient admission control algorithms without incurring any overhead at core routers. The proposed bandwidth broker architecture is designed based on a
core stateless
virtual time reference system developed in [20].
A protocol-independent technique for eliminating redundant network traffic
Authors: Spring Neil T. , Wetherall David
Published: October 2004

We present a technique for identifying repetitive information transfers and use it to analyze the redundancy of network traffic. Our insight is that dynamic content, streaming media and other traffic that is not caught by today's Web caches is nonetheless likely to derive from similar information. We have therefore adapted similarity detection techniques to the problem of designing a system to eliminate redundant transfers. We identify repeated byte ranges between packets to avoid retransmitting the redundant data.

We find a high level of redundancy and are able to detect repetition that Web proxy caches are not. In our traces, after Web proxy caching has been applied, an additional 39% of the original volume of Web traffic is found to be redundant. Moreover, because our technique makes no assumptions about HTTP protocol syntax or caching semantics, it provides immediate benefits for other types of content, such as streaming media, FTP traffic, news and mail.
Delayed Internet routing convergence
Authors: Labovitz Craig , Ahuja Abha , Bose Abhijit , Jahanian Farnam
Published: October 2004

This paper examines the latency in Internet path failure, failover and repair due to the convergence properties of inter-domain routing. Unlike switches in the public telephony network which exhibit failover on the order of milliseconds, our experimental measurements show that inter-domain routers in the packet switched Internet may take tens of minutes to reach a consistent view of the network topology after a fault. These delays stem from temporary routing table oscillations formed during the operation of the BGP path selection process on Internet backbone routers. During these periods of
delayed convergence
, we show that end-to-end Internet paths will experience intermittent loss of connectivity, as well as increased packet loss and latency. We present a two-year study of Internet routing convergence through the experimental instrumentation of key portions of the Internet infrastructure, including both passive data collection and fault-injection machines at major Internet exchange points. Based on data from the injection and measurement of several hundred thousand inter-domain routing faults, we describe several unexpected properties of convergence and show that the measured upper bound on Internet inter-domain routing convergence delay is an order of magnitude slower than previously thought. Our analysis also shows that the upper theoretic computational bound on the number of router states and control messages exchanged during the process of BGP convergence is factorial with respect to the number of autonomous systems in the Internet. Finally, we demonstrate that much of the observed convergence delay stems from specific router vendor implementation decisions and ambiguity in the BGP specification.
FIRE
Authors: Partridge Craig , Snoeren Alex C. , Strayer W. Timothy , Schwartz Beverly , Condell Matthew , Castiñeyra Isidro
Published: October 2004

Current routing protocols are monolithic, specifying the algorithm used to construct forwarding tables, the metric used by the algorithm (generally some form of hop-count), and the protocol used to distribute these metrics as an integrated package. The Flexible Intra-AS Routing Environment (FIRE) is a link-state, intra-domain routing protocol that decouples these components. FIRE supports run-time-pro- grammable algorithms and metrics over a secure link-state distribution protocol. By allowing the network operator to dynamically reprogram both the information being advertised and the routing algorithm used to construct forwarding tables in Java, FIRE enables the development and deployment of novel routing algorithms without the need for a new protocol to distribute state. FIRE supports multiple concurrent routing algorithms and metrics, each constructing separate forwarding tables. By using operator-specified packet filters, separate classes of traffic are routed using completely different routing algorithms, all supported by a single routing protocol.
A stochastic model of TCP/IP with stationary random losses
Authors: Altman Eitan , Avrachenkov Konstantin , Barakat Chadi
Published: October 2004

We present a technique for identifying repetitive information transfers and use it to analyze the redundancy of network traffic. Our insight is that dynamic content, streaming media and other traffic that is not caught by today's Web caches is nonetheless likely to derive from similar information. We have therefore adapted similarity detection techniques to the problem of designing a system to eliminate redundant transfers. We identify repeated byte ranges between packets to avoid retransmitting the redundant data.
On the propagation of long-range dependence in the Internet
Authors: Veres A. , Molnár Kenesi S. , Vattay G.
Published: October 2004

This paper analyzes how TCP congestion control can propagate self-similarity between distant areas of the Internet. This property of TCP is due to its congestion control algorithm, which adapts to self-similar fluctuations on several timescales. The mechanisms and limitations of this propagation are investigated, and it is demonstrated that if a TCP connection shares a bottleneck link with a self-similar background traffic flow, it propagates the correlation structure of the background traffic flow above a characteristic timescale. The cut-off timescale depends on the end-to-end path properties, e.g., round-trip time and average window size. It is also demonstrated that even short TCP connections can propagate long-range correlations effectively. Our analysis reveals that if congestion periods in a connection's hops are long-range dependent, then the end-user perceived end-to-end traffic is also long-range dependent and it is characterized by the largest Hurst exponent. Furthermore, it is shown that self-similarity of one TCP stream can be passed on to other TCP streams that it is multiplexed with. These mechanisms complement the widespread scaling phenomena reported in a number of recent papers. Our arguments are supported with a combination of analytic techniques, simulations and statistical analyses of real Internet traffic measurements.
Memory-efficient state lookups with fast updates
Authors: Sikka Sandeep , Varghese George
Published: October 2004

Routers must do a best matching prefix lookup for every packet; solutions for Gigabit speeds are well known. As Internet link speeds higher, we seek a scalable solution whose speed scales with memory speeds while allowing large prefix databases. In this paper we show that providing such a solution requires careful attention to
memory allocation
and
pipelining
. This is because fast lookups require on-chip or off-chip SRAM which is limited by either expense or manufacturing process. We show that doing so while providing guarantees on the number of prefixes supported requires new algorithms and the breaking down of traditional abstraction boundaries between hardware and software. We introduce new problem-specific memory allocators that have provable memory utilization guarantees that can reach 100%; this is contrast to all standard allocators that can only guarantee 20% utilization when the requests can come in the range [1 ... 32]. An optimal version of our algorithm requires a new (but feasible) SRAM memory design that allows shifted access in addition to normal word access. Our techniques generalize to other IP lookup schemes and to other state lookups besides prefix lookup.
An automatic object-oriented parser generator for Ada
Authors: Carlisle Martin C.
Published: October 2004

Although many parser generator tools (aka compiler compilers) are available, very few create a parse tree. Instead, the user must add actions to the grammar to create the parse tree. This is a tedious, mechanical task, which could easily be automated. We propose a simple scheme to map a grammar to an object-oriented hierarchy, and provide a tool, called AdaGOOP, that creates lexer and parser specifications complete with all of the actions necessary to create the parse tree.
Reprints from Computing Reviews
Authors: Seiferas Joel
Published: October 2004

As a service to our readers,
SIGACT News
has an agreement with
Computing Reviews
to reprint reviews of books and articles of interest to the theoretical computer science community.
Computing Reviews
is a monthly journal that publishes critical reviews on a broad range of computing subjects, including models of computation, formal languages, computational complexity theory, analysis of algorithms, and logics and semantics of programs. ACM members can receive a subscription to
Computing Reviews
for $46 per year by writing to ACM headquarters.
Computational geometry column 39
Authors: O'Rourke Joseph
Published: October 2004

The resolution of a decades-old open problem is described: polygonal chains cannot lock in the plane.
Experiences teaching concurrency in Ada
Authors: Leach Ronald J.
Published: October 2004

Many students have great difficulty understanding concurrent programming at anything but the most superficial level. In this paper, we describe some experience teaching concurrent programming in Ada and give some suggestions for implementing the ideas discussed here.
Ada compiler selection for embedded targets
Authors: Tetewsky A. , Racine R.
Published: October 2004

Although mainframe Ada compilers have reached execution as well as reliability performance characteristics of languages such as FORTRAN, the same is not true of embedded system compilers. Finding a reliable cross-compiler for widely used and powerful micro-processors such as the Motorola 68000 family is extremely difficult, if not impossible. First quarter '87 cross-compiler users face many tough trade-offs and additional project costs due to time lost developing compiler work-arounds. Although the user community appreciates the technological challenges of building an Ada compiler, it is still faced with trying to use incomplete and somewhat unstable systems while trying to deliver efficient, ultra-reliable code. In order to help both vendors and users alike, this article presents a set of evaluation criteria that may be used in selecting an Ada compiler for embedded system applications. Given the progress made with mainframe compilers, the major focus is on robustness, reliability, run-time system, and cross-compiler tools.
An architecture for the direct execution of the Forth programming language
Authors: Hayes John R. , Fraeman Martin E. , Williams Robert L. , Zaremba Thomas
Published: October 2004

We have developed a simple direct execution architecture for a 32 bit Forth microprocessor. The processor can directly access a linear address space of over 4 gigawords. Two instruction types are defined; a subroutine call, and a user defined microcode instruction. On-chip stack caches allow most Forth primitives to execute in a single cycle.
The effect of instruction set complexity on program size and memory performance
Authors: Davidson Jack W. , Vaughan Richard A.
Published: October 2004

One potential disadvantage of a machine with a reduced instruction set is that object programs may be substantially larger than those for a machine with a richer, more complex instruction set. The main reason is that a small instruction set will require more instructions to implement the same function. In addition, the tendency of RISC machines to use fixed length instructions with a few instruction formats also increases object program size. It has been conjectured that the resulting larger programs could adversely affect memory performance and bus traffic. In this paper we report the results of a set of experiments to isolate and determine the effect of instruction set complexity on cache memory performance and bus traffic. Three high-level language compilers were constructed for machines with instruction sets of varying degrees of complexity. Using a set of benchmark programs, we evaluated the effect of instruction set complexity had on program size. Five of the programs were used to perform a set of trace-driven simulations to study each machine's cache and bus performance. While we found that the miss ratio is affected by object program size, it appears that this can be corrected by simplying increasing the size of the cache. Our measurements of bus traffic, however, show that even with large caches, machines with simple instruction sets can expect substantially more main memory reads than machines with dense object programs.
An experimental coprocessor for implementing persistent objects on an IBM 4381
Authors: Georgiou C. J. , Palmer S. L. , Rosenfeld P. L.
Published: October 2004

In this paper we describe an experimental coprocessor for an IBM 4381 that is designed to facilitate the exploration of persistent objects.
The Mahler experience: using an intermediate language as the machine description
Authors: Wall David W. , Powell Michael L.
Published: October 2004

Division of a compiler into a front end and a back end that communicate via an intermediate language is a well-known technique. We go farther and use the intermediate language as the official description of a family of machines with simple instruction sets and addressing capabilities, hiding some of the inconvenient details of the real machine from the users and the front end compilers.To do this credibly, we have had to hide not only the existence of the details but also the performance consequences of hiding them. The back end that compiles and links the intermediate language tries to produce code that does not suffer a performance penalty because of the details that were hidden from the front end compiler. To accomplish this, we have used a number of link-time optimizations, including instruction scheduling and interprocedural register allocation, to hide the existence of such idiosyncracies as delayed branches and non-infinite register sets. For the most part we have been sucessful.
A study of scalar compilation techniques for pipelined supercomputers
Authors: Weiss Shlomo , Smith James E.
Published: October 2004

This paper studies two compilation techniques for enhancing scalar performance in high-speed scientific processors: software pipelining and loop unrolling. We study the impact of the architecture (size of the register file) and of the hardware (size of instruction buffer) on the efficiency of loop unrolling. We also develop a methodology for classifying software pipelining techniques. For loop unrolling, a straightforward scheduling algorithm is shown to produce near-optimal results when not inhibited by recurrences or memory hazards. Software pipelining requires less hardware but also achieves less speedup. Finally, we show that the performance produced with a modified CRAY-1S scalar architecture and a code scheduler utilizing loop unrolling is comparable to the performance achieved by the CRAY-1S with a vector unit and the CFT vectorizing compiler.
Compiling Smalltalk-80 to a RISC
Authors: Bush William R. , Samples A. Dain , Ungar David , Hilfinger Paul N.
Published: October 2004

The Smalltalk On A RISC project at U. C. Berkeley proves that a high-level object-oriented language can attain high performance on a modified reduced instruction set architecture. The single most important optimization is the removal of a layer of interpretation, compiling the bytecoded virtual machine instructions into low-level, register-based, hardware instructions. This paper describes the compiler and how it was affected by SOAR architectural features. The compiler generates code of reasonable density and speed. Because of Smalltalk-80's semantics, relatively few optimizations are possible, but hardware and software mechanisms at runtime offset these limitations. Register allocation for an architecture with register windows comprises the major task of the compiler. Performance analysis suggests that SOAR is not simple enough; several hardware features could be efficiently replaced by instruction sequences constructed by the compiler.
RISCs vs. CISCs for Prolog: a case study
Authors: Borriello Gaetano , Cherenson Andrew R. , Danzig Peter B. , Nelson Michael N.
Published: October 2004

This paper compares the performance of executing compiled Prolog code on two different architectures under development at U. C. Berkeley. The first is the PLM, a special-purpose CISC architecture intended as a coprocessor for a host machine. The second is SPUR, a general-purpose RISC architecture that supports tagged data. Fourteen standard benchmark programs were run on both the PLM and SPUR simulators. The compiled code for SPUR was obtained by simple macro-expansion of PLM code generated by the PLM Prolog compiler. The two implementations are compared with regard to static and dynamic program size, execution speed, and memory system performance. On average, the macrocoded SPUR implementation has a static code size 14 times larger than the PLM, executes 16 times more instructions, yet requires only 2.3 times the number of machine cycles (or has the performance of 0.43 PLMs). When memory system performance is taken into account, SPUR is equivalent to 0.29 PLMs. Optimizations of the macro-expanded code and minor architectural changes to SPUR would increase this ratio to 0.53, or 0.60 for the largest benchmarks. Thus a tagged RISC architecture can execute Prolog at least half as fast as a special-purpose CISC architecture for Prolog.
A RISC architecture for symbolic computation
Authors: Kieburtz Richard B.
Published: October 2004

The G-machine is a language-directed processor architecture designed to support graph reduction as a model of computation. It can carry out lazy evaluation of functional language programs and can evaluate programs in which logical variables are used. To support these language features, the abstract machine requires tagged memory and executes some rather complex instructions, such as to evaluate a function application.This paper explores an implementation of the G-machine as a high performance RISC architecture. Complex instructions can be represented by RISC code without experiencing a large expansion of code volume. The instruction pipeline is discussed in some detail. The processor is intended to be integrated into a standard, 32-bit memory architecture. Tagged memory is supported by aggregating data with tags in a cache.
Pipelining and performance in the VAX 8800 processor
Authors: Clark Douglas W.
Published: October 2004

The VAX 8800 family (models 8800, 8700, 8550), currently the fastest computers in the VAX product line, achieve their speed through a combination of fast cycle time and deep pipelining. Rather than pipeline highly variable VAX instructions as such, the 8800 design pipelines uniform microinstructions whose addresses are generated by instruction unit hardware. This design approach helps achieve a fast cycle time, which is the prime determinan of performance. Some preliminary measurements of cycles per average instruction are reported.
Programming language impacts on learning
Authors: Hamilton J. A. Drew , Murtagh Jeanne L. , Zoller Richard G.
Published: October 2004

What programming language should be taught in an introductory computer science course? Studies and experiences at West Point provide some insight into these questions. This paper reports the statistical results obtained from a side-by-side comparison of Pascal and Ada. The unique nature of our institution provided the opportunity to isolate and study causal factors, and allowed us to follow the experimental and control groups through graduation.We conducted a side by side comparison of the use of Pascal, which was specifically designed for instructional purposes, and Ada in an introductory course. The experiment demonstrated that students were much more successful in Ada than in Pascal, and led to the revision of the Academy core curriculum to use Ada 95 in our introductory computer science class. This paper discusses the details of our comparison, citing specific examples to illustrate a rational basis for evaluating programming language features.
An Ada interface to lego mindstorms
Authors: Fagin Barry
Published: October 2004

This article presents an Ada interface to the Lego Mindstorms
TM
RCX "brick", the core element of a commercial product that emerged from a collaboration between the Lego Corporation and MIT's Media Laboratory. Since its arrival on the market in 1998, it has considerable interest in the computing community: a variety of operating systems and language interfaces are available for it, all provided free of charge by people who simply wanted to find out how the RCX workedThe interface described here is in use at the Air Force Academy as part of an experiment in computer science education. Students with no prior programming background are given a pre-built Mindstorms robot and a series of programming challenges, which they then attempt to implement using Ada. Our hope is that the experience of programming robots will provide an effective, efficient, and enjoyable method for conveying essential computer science concepts. We are currently attempting to assess its effectiveness, and hope to present our results at a future date.
Ada/Mindstorms 1.0 User's Guide and Reference Manual
Authors: Fagin Barry
Published: October 2004

Ada/Mindstorms 1.0 is an Ada interface to the Lego RCX "brick", included as part of the Lego Mindstorms Robotics Invention System. Programs are written with an Ada compiler, translated into Dave Baum's Not Quite C langauge (NQC), then recompiled and downloaded through the Mindstorms IR transmitter to the RCX.Ada/Mindstorms 1.0 is distributed with the USAFA AdaGIDE Windows Ada compiler. This document assumes that you have obtained and installed AdaGIDE. If you are using another Ada compiler, see Appendix A. We also assume working knowledge of Ada. If you haven't used Ada before, we recommend learning the basics first before reading further, http://www.adahome.com/Discover/Introduction.html is a good place to start. We also assume a general familiarity with the Lego Mindstorms Robotics Invention System and the RCX.To use Ada/Mindstorms 1.0, you need a PC running Windows and a Windows Ada compiler. To download Ada/Mindstorms programs to an RCX and test them, you need:1 Dave Baum's NQC system installed on your PC. It's available from http://www.enteract.com/-dbaum/nqc/index.html. If you're using AdaGIDE, the file nqc.exe executable needs to be in c:\gnatpro\bin so that AdaGIDE can find it. Otherwise it can be anywhere convenient.2 A Lego RCX brick pre-loaded with Mindstorms firmware.3 A Lego I/R transmitter hooked up to your PC's serial port. These come standard with the Lego Mindstorms Robotics Invention System.If you have already purchased a Lego Mindstorms Robotics Invention System, you don't need the CD/ROM and software that come with the it. Ada/Mindstorms is a separate programming environment, replacing the Mindstorms graphical programming tools with an Ada interface.
OSI addressing strategies
Authors: Jakobs K.
Published: October 2004

The paper presents a survey of addressing principles of the OSI/RM. Relevant OSI-specific terms and mechanisms are explained; the addressing capabilities of the seven layers are described.
A model to order the encryption algorithms according to their quality
Authors: Prieto A. R. , Tomas J. G.
Published: October 2004

Usually the unicity distance is used to give the strength of encryption algorithms. In this work, the behaviour of encipherment algorithm has been analyzed and two different parameters are proposed in order to evaluate the quality. These parameters are checked against the unicity distance and a final test has been executed, using DES.
Address resolution for an intelligent filtering bridge running on a subnetted ethernet system
Authors: Parr G.
Published: October 2004

When a generic host goes down or moves on a subnetted configuration on Ethernets running, for example TCP/IP, and comes back up again, with either a completely new network interface, or a newly assinged protocol address, this information is not currenlty available to remote hosts/devices on the system. What I propose here is a facility whereby all connected systems can be informed of this "REBOOT" situation as soon as it is detected by its neighbouring Bridge. This way, subsequent redundant, and wasteful transmissions can be prevented taking place from remote sources to 'unobtainable' hosts. A broadcast medium such as Ethernet is assumed.
Scheduling difficulties of Ada in the hard real-time environment
Authors: McCormick Frank
Published: October 2004

The tasking model in Ada suffers from several limitations which make scheduling strategies cumbersome for many embedded systems. This paper discusses the timing needs of one class of these systems and describes a plausible response to the problems.
A model for a portable Ada run-time library
Authors: Landwehr Rudolf , Heensel Peter , Bayan Rami , Kung Antonio
Published: October 2004

A model for a portable and efficient Ada run-time library is presented that supports Ada tasking for real-time applications. After an overview of the module structure, the interface of a compiler-independent, real-time kernel is discussed in more detail. Finally, we evaluate the model based on an implementation on Motorola MC68000.
Building partitioned architectures based on the Ravenscar profile
Authors: Dobbing Brian
Published: October 2004

The requirement to support software partitioning is a recurring theme within High Integrity and Safety Critical systems. The partition concept is used to implement differing access protection levels for applications of varying criticality levels executing on the same processor. Partitions can also be used in fault tolerant systems that require high availability, redundancy or dynamic re-configuration.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 and deterministic real-time software.This paper describes how a COTS Ada95 compilation system that implements the Ravenscar Profile can be used in the implementation of a partitioned architecture in an Integrated Modular Avionics context based on the ARINC 653 Application Executive (APEX) standard.