bluuebunny/crossref_metadata_2025 huggingface dataset:
User-level threads on a general hardware interface
Authors: Mayes K. R. , Quick S. , Warboys B. C.
Published: October 2004

Moving resource management out of the operating system kernel facilitates a high degree of customisation. The lowest layer of the Arena system provides an abstract interface to conventional processor hardware (Mayes, 1993; Quick, 1995). The idea is to encapsulate the hardware behind an interface with certain low-level concepts which are generally applicable to any processor. Localization of hardware-dependency has the effect of increasing modularity and thus portability. This encapsulation, termed the Arena hardware object (HWO) supports portable user-level customizable resource management (Mayes et al., 1994). The aim is to remove resource management policy from the HWO whilst maintaining its integrity. The present paper deals with the Arena approach to the provision of pure user-level threads. Native implementations on Sparc and i486 processors are briefly described and performance figures are given. The compromise between reducing policy and maintaining integrity in the HWO implementations is discussed.
Reflection of developing user-level real-time thread packages
Authors: Oikawa Shuichi , Tokuda Hideyuki
Published: October 2004

In multimedia environments, applications use continuous-media data, such as video data and audio data, to provide users with a wide variety of interaction schemes with computers. Continuous-media applications require more efficient and flexible support from real-time threads than such research real-time systems. To fulfill such requirements, we have been developing user-level real-time threads, which are real-time threads implemented at the user level.We have implemented two user-level real-time thread packages on different operating system platforms, ARTS and RT-Mach. There were several issues, which we considered to design their architectures, such as compatibility, performance, correctness and accuracy. This paper describes the design issues, the lessons we have learned, and the discussions on their development.
Computational geometry column 27
Authors: O'Rourke Joseph
Published: October 2004

The following new result is discussed: there is a perfect matching between the edges of any two triangulations of a finite set of points in the plane.
Sporadic tasks in hard real-time systems
Authors: Allen R. K. , Burns A. , Wellings A. J.
Published: October 2004

In this paper, we illustrate how systems containing hard real-time sporadic tasks can be analysed for their worst case behaviour. In order to undertake this schedulability analysis, it is necessary to define the minimum inter-arrival time and/or maximum arrival frequency of sporadic tasks. Furthermore, at run-time it is essential to ensure that sporadic tasks are not invoked more often than has been guaranteed by the analysis. We assume that sporadics are invoked by interrupts and that interrupts can be masked under software control.
Institutional impacts on decision support system research
Authors: Holsapple Clyde W. , Luo Wenhong
Published: October 2004

This research extends a recent study that ranked the contributions of doctoral MIS institutions to decision support system research. That ranking was based on the frequency with which work of an institution's faculty has been cited in reference lists of a large set of DSS journal articles appearing over a 20-year period. We contend that this frequency measure of an institution's contribution is only one way of measuring its impact on decision support system research. Another impact measure involves the potency of an institution's contributions. Here, we develop an institutional ranking based on this alternative impact measure. Results of the frequency and potency rankings are then combined into an overall impact index for assessing relative contributions. Finally, we normalize the impact rankings with respect to faculty size.
Information systems skills
Authors: Ng Tye Eugenia M. W. , Poon Ray S. K. , Burn Janice M.
Published: October 2004

The objectives of this study are to find out the perceived information systems (IS) skills which are important at present and in five years time, and the perceived emphasis of IS curricula on these skills. It is found that the scope of skills required of IS professionals will broaden towards the end of the decade. Interpersonal skills, business skills, analysis and design skills, and programming skills are the most critical for career development. Results also show that there is a match between the skills and knowledge possessed by IS graduates of the Hong Kong Polytechnic University and industry requirements for the current IS environment. However, the curriculum is not aligned with industry needs in the future. This indicates that the education the respondents received does not prepare them for progression up the career ladder. Implications of the findings are discussed so that a new curriculum may be designed to provide the preferred IS graduates to industry.
Implementing self-reproducing artificial organisms with Ada
Authors: Laval Philippe
Published: October 2004

Artificial Life techniques have a potential use in ecological models, but they have not yet been programmed in Ada. Ada tasks provide a powerful means to express the behavior of self-reproductive autonomous individuals. This article shows how artificial organisms with a complicated reproduction (alternation of sexual and asexual generations) have been implemented in an ecological simulation software written in Ada.
ASIS for GNAT
Authors: Rybin Sergey , Strohmeier Alfred , Zueff Eugene
Published: October 2004

This article describes the approach taken to implement the Ada Semantic Interface Specification (ASIS) for the GNAT Ada compiler. The paper discusses the main implementation problems and their solutions. It also describes the current state of the implementation. This is a slightly revised version of the paper published in the proceedings of the Ada-Europe'95 conference.
SIGACT News Complexity Theory Column 12
Authors: Hemaspaandra Lane A.
Published: October 2004

Please don't be shy about sending even vague pointers to people who may have complete or partial resolutions of the problems mentioned in any of the open questions columns that have appeared as earlier complexity theory columns. Though I don't give a dollar for each solved problem (what do you expect on a theoretician's salary!), I'll be delighted to report in this space on resolutions (such as the thrilling resolution by Cai and Sivakumar that was mentioned in the previous column). Without further delay, here is this issue's guest column, by Mihir Bellare.
Joint actions based authorization schemes
Authors: Varadharajan Vijay , Allen Phillip
Published: October 2004

Authorization policy requirements in commercial applications are often richer compared to military applications in terms of the types of privileges required, and more complex in terms of both the nature and degree of interactions between participating objects. Delegation and joint action mechanisms allow a more flexible and dynamic form of access control, thereby enabling the representation of sophisticated authorization policies. This paper explores some issues that need to be addressed when designing such joint actions based authorization policies. We describe some approaches to supporting joint actions based authorization policies, and their ramifications for trust of various components of the implementation. We consider an example from the medical field, and define attributes relevant to the design of joint action schemes and present three schemes for supporting joint action based authorization policies.
A high performance and adaptive commit protocol for a distributed environment
Authors: Panadiwal Rajmohan , Goscinski Andrzej M.
Published: October 2004

In this paper a high performance and adaptive commit protocol is presented. The proposed protocol is the result of research into developing a very important relationship between the file storage strategy and techniques to commit transactions. It is demonstrated that the proposed protocol is capable of combining the powers of different methods for committing transactions.
Real-time scheduling of multimedia data retrieval to minimize buffer requirement
Authors: Tsai Wen-Jiin , Lee Suh-Yin
Published: October 2004

Continuous display is an important issue in the domain of multimedia applications. Especially, to ensure this continuity in the presence of multiusers, a feasible scheduling algorithm is prerequisite for real time data retrieval from the I/O subsystem. I/O scheduling techniques can be classified into two types:
meta-I/O scheduling
which arranges the sequence of data retrieval before issuing physical I/O requests, and
disk scheduling
which determines the order of processing I/O requests that have been issued. In
disk scheduling,
there are several elegant algorithms that had been discussed such as Scan, C-Scan, shortest seek time first and Scan-EDF. All of them focused on improving I/O throughput by serving requests closer to disk head first [7][8]. We focus this paper, however, on solving the real time meta-I/O scheduling.For real-time scheduling, several algorithms had been addressed such as earliest-deadline-first (EDF) [4], least-laxity-first (LLF) [9], earliest-ready-time first (LRF) [6], and so on, which had shown to be elegant for task scheduling to promote system throughput. When applying to meta-I/O scheduling, however, these algorithms would result in large amount of buffer requirement for accommodating the retrieved data. In this paper, we proposed two real-time algorithms and a technique, called
object migration,
to minimize buffer requirement for meta-I/O scheduling. A buffer measurement approach was also proposed in this paper to estimate the performance of a real-time scheduling algorithm, which is based upon the well-known graph coloring technique. Simulation experiments were conducted to analyze the performance of algorithms. The results indicate that our approaches perform much better than existing real-time algorithms in terms of reducing buffer requirement.
On the performance of bandwidth allocation strategies for interconnecting ATM and connectionless networks
Authors: Chan Edward , Lee Victor C. S. , Ng Jim M.
Published: October 2004

Using ATM networks as the switching fabric for interconnecting LANs and MANs means that a strategy for bandwidth allocation must be developed to map connectionless traffic in the LAN/MAN to the ATM network which is essentially connection-oriented. This paper presents a bandwidth allocation algorithm based on bandwidth advertising and burst drop when overflow occurs. The performance is evaluated by simulation and shown to reduce Burst Loss Rate significantly.
Measuring IS
Authors: Smith H. A. , McKeen J. D.
Published: October 2004

In today's difficult economy, companies are reorganizing and streamlining wherever possible in order to save money and attract customers. This new corporate emphasis on better organizational performance, i.e., both productivity and quality goods and services, challenges all parts of an organization, including IS, to make improvements in what they do and how they operate. This is easier said than done and many organizations are having difficulties knowing where to start, what to do, and what their goals should be. Organizational learning change are the hallmarks of business in the nineties and the starting point for this effort is the collection of accurate and adequate information and its appropriate analysis.It is not surprising therefore that comparison, measurement, and evaluation have become something of a preoccupation in many businesses in recent years. The U.S. National Quality Institute, (which establishes the detailed criteria for the Malcolm Baldridge Awards), suggests there are three components of effective information and analysis which act as the "brain center" driving the corporate improvement effort, regardless of a company's organization or structure (Baldridge Criteria, 1993):1. Scope and management of quality and performance information.2. Collection, analysis, and use of company level data, including customer data and operations data, and linking performance data to overall financial performance.3. Competitive comparisons and benchmarking.These criteria can also be used by individual corporate subunits to determine how well they contribute to overall quality and performance.One organizational subunit receiving a considerable amount of executive attention in this regard is the information systems (IS) function. Many companies are looking to information technology to help them support corporate restructuring, but to do it with increasingly fewer resources. Unfortunately, IS has also been an area of the company that has been extremely difficult to measure and evaluate. IS also continues to have a credibility problem in some organizations where executives believe that IS has contributed little or nothing to the corporate bottom line (Roach, 1989). As well, there are still many users who tend to feel that IS service is lacking or could be bought cheaper elsewhere. With IS budgets coming under closer and closer scrutiny, IS itself is placing new emphasis on measurement to demonstrate its contribution to overall corporate performance, both through quality services and systems and through its ability to do so cost-effectively.This paper looks at the three components of information and its analysis, as outlined above, from the perspective of the IS subunit. It summarizes what IS departments are doing to assess and analyze their organizations and makes suggestions about how the measurement and evaluation of IS both internally and externally could be improved.
Simulation-based comparisons of Tahoe, Reno and SACK TCP
Authors: Fall Kevin , Floyd Sally
Published: October 2004

This paper uses simulations to explore the benefits of adding selective acknowledgments (SACK) and selective repeat to TCP. We compare Tahoe and Reno TCP, the two most common reference implementations for TCP, with two modified versions of Reno TCP. The first version is New-Reno TCP, a modified version of TCP without SACK that avoids some of Reno TCP's performance problems when multiple packets are dropped from a window of data. The second version is SACK TCP, a conservative extension of Reno TCP modified to use the SACK option being proposed in the Internet Engineering Task Force (IETF). We describe the congestion control algorithms in our simulated implementation of SACK TCP and show that while selective acknowledgments are not required to solve Reno TCP's performance problems when multiple packets are dropped, the absence of selective acknowledgments does impose limits to TCP's ultimate performance. In particular, we show that without selective acknowledgments, TCP implementations are constrained to either retransmit at most one dropped packet per round-trip time, or to retransmit packets that might have already been successfully delivered.
Architectural and protocol frameworks for multicast data transport in multi-service networks
Authors: Ravindran K.
Published: October 2004

The paper presents architectural and protocol techniques for multicast transport of multi-service data (such as video, audio and graphics). A tree-structured channel in the network is employed as building block for constructing multicast transport services. Data from different sources are multiplexed over a shared tree channel for reaching destinations through intermediate network nodes and links. The choice of multicast architecture is based on the extent of sharing of common links in a tree across multi-source data flows to allow finer degree of link bandwidth allocation control and reduce the fixed cost of links for data transport. The canonical network substrate so constructed exemplifies a 'programmable network' that may be 'plugged-in' with QOS and flow parameters to instantiate the network behavior for matching the needs of each application. This philosophy is in alignment with the evolving 'Internet Service Layer' functionalities. The paper describes the functional and protocol elements of multicast architectures to support the 'programmable network' view. It also describes the salient features of an implementation embedding these architectures.
Service and network management in the OAMS open service architecture
Authors: Znaty Simon
Published: October 2004

New open service architectures are now emerging to ease service construction, management, testing, deployment, and operation, and to hide from the service designer the heterogeneity of the underlying technologies and the complexities introduced by distribution. These architectures should provide all the functionalities for call and connection management, and support management functional areas. To reach these objectives, information models must be defined which provide service and network representations by data. This paper presents the specification, design and implementation of the management architecture of OAMS which is an open service architecture. The proposed architecture is deployed over the distributed processing environment DCE
2
. It exhibits service, network and element management views by means of information models, in order to manage the end-to-end connectivity requested by telecommunication services.
The future of computational complexity theory: part I
Authors: Papadimitriou Christos H. , Goldreich Oded , Wigderson Avi , Razborov Alexander A. , Sipser Michael
Published: October 2004

As you probably already know, there is an active discussion going on---in forums ranging from lunch-table conversations to workshops on "strategic directions" to formal reports---regarding the future of theoretical computer science. Since your complexity columnist does not know The Answer, I've asked a number of people to contribute their comments on the narrower issue of the future of complexity theory. The only ground rule was a loose 1-page limit; each contributor could choose what aspect(s) of the future to address, and the way in which to address them. The first installment of contributions appears in this issue, and one or two more installments will appear among the next few issues.Also coming during the next few issues: the search for the perfect theory journal, and (for the sharp-eyed) Lance Fortnow dons a clown suit. Finally, let me mention that work of Russell Impagliazzo resolves one of the open questions from Complexity Theory Column 11.
25 years of quantum cryptography
Authors: Brassard Gilles , Crépeau Claude
Published: October 2004

The fates of
SIGACT News
and Quantum Cryptography are inseparably entangled. The exact date of Stephen Wiesner's invention of "conjugate coding" is unknown but it cannot be far from April 1969, when the premier issue of
SIGACT News
---or rather
SICACT News
as it was known at the time---came out. Much later, it was in
SIGACT News
that Wiesner's paper finally appeared [74] in the wake of the first author's early collaboration with Charles H. Bennett [7]. It was also in
SIGACT News
that the original experimental demonstration for quantum key distribution was announced for the first time [6] and that a thorough bibliography was published [19]. Finally, it was in
SIGACT News
that Doug Wiedemann chose to publish his discovery when he reinvented quantum key distribution in 1987, unaware of all previous work but Wiesner's [73, 5].Most of the first decade of the history of quantum cryptography consisted of this lone unpublished paper by Wiesner. Fortunately, Bennett was among the few initiates who knew of Wiesner's ideas directly from the horse's mouth. His meeting with the first author of this column in 1979 was the beginning of a most fruitful lifelong collaboration. It took us five more years to invent quantum key distribution [4], which is still today the best-known application of quantum mechanics to cryptography. The second author joined in slightly later, followed by a few others. But until the early 1990's, no more than a handful of people were involved in quantum cryptographic research. Since then, the field has taken off with a vengeance, starting with Artur K. Ekert's proposal to use quantum nonlocality for cryptographic purposes [33].The golden age started in earnest when Ekert organized the first international workshop on quantum cryptography in Broadway, England, in 1993. Since then, many conferences have been devoted at least partly to quantum cryptography, which has become a major international topic. The purpose of the aforementioned 1993 bibliography in
SIGACT News
was to cite as much as possible
all
papers ever written on the subject, including unpublished manuscripts: there were 57 entries in total. Today, such an undertaking would be nearly impossible owing to the explosion of new research in the field.The purpose of this column is to give an overview of the current research in quantum cryptography. It is not our intention to be exhaustive and we apologize in advance to any researcher whose work we may have omitted. Note that we do not necessarily agree with the claims in every paper mentioned here: this column should not be construed as a seal of approval!
A distributed computing model based on multiserver
Authors: Hua Ji , Li Xie
Published: October 2004

With the development of distributed system, there are many resources coexisted in the network environment. To a special kind of service, there may exist some relationships among many servers, such as equalservice, superservice and subservice. In this paper, we define this phenomenon as
Multiserver
system. Besides, We discuss the problems in Multiserver system in the view of
Open Distributed Processing(ODP),
and propose a basic open model about Multiserver system. Based on the open model, we also have implemented a prototype system(OMM) on the top of
PVM(parallel virtual machine).
With description of the architecture and behavior of the components in OMM, we can make an distributed system more transparent, interoperable and fault-tolerated.
An assessment of database research interest in MIS
Authors: Lai Vincent S.
Published: October 2004

This study focuses on the evaluation of database as a field of research and examines its intellectual evolution. An extensive literature review of articles published in MIS journals over the last fifteen years shows that MIS researchers have not placed the same level of importance on database issues as have computer scientists. MIS researchers published have only 159 database articles in thirteen of the top MIS journals during the period of 1980-1994. The majority of these articles were conceptual studies of issues that dealt with the design and management of database systems. This publication record is especially low, considering that 12.5% of MIS faculty listed in the 1989, 1992, and 1995
Directories of MIS Faculty
were interested in database research. Of all MIS journals studied,
DATA BASE
and
Information & Management
were found to be more likely than others to publish database articles.
A process oriented framework for assessing the business value of information technology
Authors: Mooney John G. , Gurbaxani Vijay , Kraemer Kenneth L.
Published: October 2004

In the current competitive environment, the need for better management of all organizational resources, and specifically IT, requires comprehensive assessment of their contribution to firm performance. However, there is little empirical evidence that IT is capable of creating value, nor has a comprehensive framework of business value emerged. Many of the available studies of IT productivity and business value were conducted using firm level output measures of value. The focus on firm level output variables, while important, provides only limited understanding of how value is created using IT. This paper develops a conceptual framework of the business value outcomes of IT by synthesizing the extant literature on IT business value and IT supported organization and process design. The framework provides a basis for process oriented studies of IT business value, and enhances our understanding of the links between information technology and firm performance.
Optimistic concurrency control for abstract data types
Authors: Herlihy Maurice
Published: October 2004

A concurrency control technique is optimistic if it allows transactions to execute without synchronization, relying on commit-time validation to ensure serializability. This paper describes several new optimistic concurrency control techniques for objects in distributed systems, proves their correctness and optimality properties, and characterizes the circumstances under which each is likely to be useful. These techniques have the following novel aspects. First, unlike many methods that classify operations only as reads or writes, these techniques systematically exploit type-specific properties of objects to validate more interleavings. Necessary and sufficient validation conditions are derived directly from an object's data type specification. Second, these techniques are modular: they can be applied selectively on a per-object (or even per-operation) basis in conjunction with standard pessimistic techniques such as two-phase locking, permitting optimistic methods to be introduced exactly where they will be most effective. Third, when integrated with quorum-consensus replication, these techniques circumvent certain trade-offs between concurrency and availability imposed by comparable pessimistic techniques. Finally, the accuracy and efficiency of validation are further enhanced by some technical improvements: distributed validation is performed as a side-effect of the commit protocol, and validation takes into account the results of operations, accepting certain interleavings that would have produced delays in comparable pessimistic schemes.
Development and implementation of the Magnavox generic Ada basic mathematics package
Authors: Rehmer K
Published: October 2004

This paper explains development work on a mathematics library at Magnavox during the summer of 1985 and some revisions which were made in the early summer of 1986. Briefly, sources for a basic mathematics library will be explored, reasons behind some of the design decisions made will be discussed. Finally, a brief presentation of the method of testing will be given.
ASHs
Authors: Wallach Deborah A. , Engler Dawson R. , Kaashoek M. Frans
Published: October 2004

Application-specific safe message handlers (ASHs)
are designed to provide applications with hardware-level network performance. ASHs are user-written code fragments that safely and efficiently execute in the kernel in response to message arrival. ASHs can direct message transfers (thereby eliminating copies) and send messages (thereby reducing send-response latency). In addition, the ASH system provides support for dynamic integrated layer processing (thereby eliminating duplicate message traversals) and dynamic protocol composition (thereby supporting modularity). ASHs provide this high degree of flexibility while still providing network performance as good as, or (if they exploit application-specific knowledge) even better than, hard-wired in-kernel implementations. A combination of user-level microbenchmarks and end-to-end system measurements using TCP demonstrate the benefits of the ASH system.
Phantom
Authors: Afek Yehuda , Mansour Yishay , Ostfeld Zvi
Published: October 2004

This paper presents
Phantom
, a simple constant space algorithm for rate based flow control. As shown by our simulations, it converges fast to a fair rate allocation while generating a moderate queue length. While our approach can be easily implemented in ATM switches for managing ABR traffic, it is also suitable for flow control in TCP router based networks. Both the introduced overhead and the required modifications in TCP flow control systems are minimal. The implementation of this approach in TCP guarantees fairness and provides a unifying interconnection between TCP routers and ATM networks. The new algorithm easily inter-operates with current TCP flow control mechanisms and thus can be gradually introduced into installed based TCP networks.
Multicasting protocols for high-speed, wormhole-routing local area networks
Authors: Gerla Mario , Palnati Prasasth , Walton Simon
Published: October 2004

Wormhole routing LANs are emerging as an effective solution for high-bandwidth, low-latency interconnects in distributed computing and cluster computing applications. An important example is the 640 Mb/s crossbar-based Myrinet. A key property of conventional LANs, which is valuable for many distributed applications, is transparent, reliable network-level multicast. It is desirable to retain this property also in wormhole LANs. Unfortunately, efficient, reliable multicasting in wormhole LANs is problematic because of the potential for deadlocks. As a consequence, current multicasting implementations typically consist of repeated unicast or assume a priori buffer reservations. These solutions, however, tend to increase latency and do not scale well.In this paper we address the problem of providing transparent, reliable, efficient network level multicasting in the wormhole LAN. We describe several protocols for achieving deadlock-free, reliable multicasting using restricted routing and fast buffer reservation techniques. Tradeoffs involving complexity and performance of various solutions are discussed, and are illustrated using simulation. A simple multicast implementation for Myrinet has been carried out, and experimental results are presented.
Simulation study of the capacity effects of dispersity routing for fault tolerant realtime channels
Authors: Banerjea Anindo
Published: October 2004

The paper presents a simulation study of the use of dispersity routing to provide fault tolerance on top of a connection oriented realtime service such as that provided by the Tenet scheme. A framework to study the dispersity schemes is presented. The simulations show that the dispersity schemes, by dividing the connection's traffic among multiple paths in the network, have a beneficent effect on the capacity of the network. Thus, for certain classes of dispersity schemes, we obtain a small improvement in fault tolerance as well as an improvement in the number of connections that the network can support. For other classes of dispersity schemes, greater improvement in service may be purchased at the cost of decrease in capacity. The paper explores the tradeoffs available through exhaustive simulations. We conclude that dispersity routing is a flexible approach to increasing the fault tolerance of realtime connections, which can provide a range of improvements in service with a corresponding range of costs.
A channel access scheme for large dense packet radio networks
Authors: Shepard Timothy J.
Published: October 2004

Prior work in the field of packet radio networks has often assumed a simple success-if-exclusive model of successful reception. This simple model is insufficient to model interference in large dense packet radio networks accurately. In this paper we present a model that more closely approximates communication theory and the underlying physics of radio communication. Using this model we present a decentralized channel access scheme for scalable packet radio networks that is free of packet loss due to collisions and that at each hop requires no per-packet transmissions other than the single transmission used to convey the packet to the next-hop station. We also show that with a modest fraction of the radio spectrum, pessimistic assumptions about propagation resulting in maximum-possible self-interference, and an optimistic view of future signal processing capabilities that a self-organizing packet radio network may scale to millions of stations within a metro area with raw per-station rates in the hundreds of megabits per second.
Adaptive resource management algorithms for indoor mobile computing environments
Authors: Lu Songwu , Bharghavan Vaduvur
Published: October 2004

Emerging indoor mobile computing environments seek to provide a user with an advanced set of communication-intensive applications, which require sustained quality of service in the presence of wireless channel error, user mobility, and scarce available resources. In this paper, we investigate two related approaches for the management of critical networking resources in indoor mobile computing environments:• adaptively re-adjusting the quality of service within pre-negotiated bounds in order to accommodate network dynamics and user mobility.• classifying cells based on location and handoff profiles, and designing advance resource reservation algorithms specific to individual cell characteristics.Preliminary simulation results are presented in order to validate the approaches for algorithmic design. A combination of the above approaches provide the framework for resource management in an ongoing indoor mobile computing environment project at the University of Illinois.
A comparison of mechanisms for improving TCP performance over wireless links
Authors: Balakrishnan Hari , Padmanabhan Venkata N. , Seshan Srinivasan , Katz Randy H.
Published: October 2004

Reliable transport protocols such as TCP are tuned to perform well in traditional networks where packet losses occur mostly because of congestion. However, networks with wireless and other lossy links also suffer from significant non-congestion-related losses due to reasons such as bit errors and handoffs. TCP responds to all losses by invoking congestion control and avoidance algorithms, resulting in degraded end-to-end performance in wireless and lossy systems. In this paper, we compare several schemes designed to improve the performance of TCP in such networks. These schemes are classified into three broad categories: end-to-end protocols, where the sender is aware of the wireless link; link-layer protocols, that provide local reliability; and split-connection protocols, that break the end-to-end connection into two parts at the base station. We present the results of several experiments performed in both LAN and WAN environments, using throughput and goodput as the metrics for comparison.Our results show that a reliable link-layer protocol with some knowledge of TCP provides very good performance. Furthermore, it is possible to achieve good performance without splitting the end-to-end connection at the base station. We also demonstrate that selective acknowledgments and explicit loss notifications result in significant performance improvements.
Whole-program optimization for time and space efficient threads
Authors: Grunwald Dirk , Neves Richard
Published: October 2004

Modern languages and operating systems often encourage programmers to use
threads,
or independent control streams, to mask the overhead of some operations and simplify program structure. Multitasking operating systems use threads to mask communication latency, either with hardwares devices or users. Client-server applications typically use threads to simplify the complex control-flow that arises when multiple clients are used. Recently, the scientific computing community has started using threads to mask network communication latency in massively parallel architectures, allowing computation and communication to be overlapped. Lastly, some architectures implement threads in hardware, using those threads to tolerate memory latency.In general, it would be desirable if threaded programs could be written to expose the largest degree of parallelism possible, or to simplify the program design. However, threads incur time and space overheads, and programmers often compromise simple designs for performance. In this paper, we show how to reduce time and space thread overhead using control flow and register liveness information inferred
after
compilation. Our techniques work on binaries, are not specific to a particular compiler or thread library and reduce the the overall execution time of fine-grain threaded programs by ≈ 15-30%. We use execution-driven analysis and an instrumented operating system to show why the execution time is reduced and to indicate areas for future work.
Thread scheduling for cache locality
Authors: Philbin James , Edler Jan , Anshus Otto J. , Douglas Craig C. , Li Kai
Published: October 2004

This paper describes a method to improve the cache locality of sequential programs by scheduling fine-grained threads. The algorithm relies upon hints provided at the time of thread creation to determine a thread execution order likely to reduce cache misses. This technique may be particularly valuable when compiler-directed tiling is not feasible. Experiments with several application programs, on two systems with different cache structures, show that our thread scheduling method can improve program performance by reducing second-level cache misses.
Petal
Authors: Lee Edward K. , Thekkath Chandramohan A.
Published: October 2004

The ideal storage system is globally accessible, always available, provides unlimited performance and capacity for a large number of clients, and requires no management. This paper describes the design, implementation, and performance of Petal, a system that attempts to approximate this ideal in practice through a novel combination of features. Petal consists of a collection of network-connected servers that cooperatively manage a pool of physical disks. To a Petal client, this collection appears as a highly available block-level storage system that provides large abstract containers called
virtual disks.
A virtual disk is globally accessible to all Petal clients on the network. A client can create a virtual disk on demand to tap the entire capacity and performance of the underlying physical resources. Furthermore, additional resources, such as servers and disks, can be automatically incorporated into Petal.We have an initial Petal prototype consisting of four 225 MHz DEC 3000/700 workstations running Digital Unix and connected by a 155 Mbit/s ATM network. The prototype provides clients with virtual disks that tolerate and recover from disk, server, and network failures. Latency is comparable to a locally attached disk, and throughput scales with the number of servers. The prototype can achieve I/O rates of up to 3150 requests/sec and bandwidth up to 43.1 Mbytes/sec.
The intrinsic bandwidth requirements of ordinary programs
Authors: Huang Andrew S. , Shen John Paul
Published: October 2004

While there has been an abundance of recent papers on hardware and software approaches to improving the performance of memory accesses, few papers have addressed the problem from the program's point of view. There is a general notion that certain programs have larger working sets than others. However, there is no quantitative method for evaluating and comparing the memory requirements of programs.This paper introduces the
bandwidth spectrum
for characterizing the memory requirements of a program's instruction and data stream. The bandwidth spectrum measures the average bandwidth requirement of a program as a function of available local memory. These measurements are performed under the most idealized conditions of perfect knowledge and perfect memory management. As such, they represent the lower bounds on the memory requirements of programs. We present the bandwidth spectrums for a set of 22 benchmarks and show how they can be used in the comparison of memory requirements and I/O requirement. The bandwidth spectrums also offer a convenient method to weigh the trade-off amongst instruction issue rate, local memory capacity and bandwidth into local memory.Using the bandwidth spectrum, we show that at issue rates of four or less, bandwidth usually scales linearly with the issue rate. At higher issue rates, bandwidth can often scale superlinearly with respect to issue rate. Finally, we also investigate the effects of varying the input sets on the bandwidth spectrums.
Adapting to network and client variability via on-demand dynamic distillation
Authors: Fox Armando , Gribble Steven D. , Brewer Eric A. , Amir Elan
Published: October 2004

The explosive growth of the Internet and the proliferation of smart cellular phones and handheld wireless devices is widening an already large gap between Internet clients. Clients vary in their hardware resources, software sophistication, and quality of connectivity, yet server support for client variation ranges from relatively poor to none at all. In this paper we introduce some design principles that we believe are fundamental to providing "meaningful" Internet access for the entire range of clients. In particular, we show how to perform on-demand datatype-specific lossy compression on semantically typed data, tailoring content to the specific constraints of the client. We instantiate our design principles in a proxy architecture that further exploits typed data to enable application-level management of scarce network resources. Our proxy architecture generalizes previous work addressing all three aspects of client variation by applying well-understood techniques in a novel way, resulting in quantitatively better end-to-end performance, higher quality display output, and new capabilities for low-end clients.
SoftFLASH
Authors: Erlichson Andrew , Nuckolls Neal , Chesson Greg , Hennessy John
Published: October 2004

One potentially attractive way to build large-scale shared-memory machines is to use small-scale to medium-scale shared-memory machines as clusters that are interconnected with an off-the-shelf network. To create a shared-memory programming environment across the clusters, it is possible to use a virtual shared-memory software layer. Because of the low latency and high bandwidth of the interconnect available within each cluster, there are clear advantages in making the clusters as large as possible. The critical question then becomes whether the latency and bandwidth of the top-level network and the software system are sufficient to support the communication demands generated by the clusters.To explore these questions, we have built an aggressive kernel implementation of a virtual shared-memory system using SGI multiprocessors and 100Mbyte/sec HIPPI interconnects. The system obtains speedups on 32 processors (four nodes, eight processors per node plus additional reserved protocol processors) that range from 6.9 on the communication-intensive FFT program to 21.6 on Ocean (both from the SPLASH 2 suite). In general, clustering is effective in reducing internode miss rates, but as the cluster size increases, increases in the remote latency, mostly due to increased TLB synchronization cost, offset the advantages. For communication-intensive applications, such as FFT, the overhead of sending out network requests, the limited network bandwidth, and the long network latency prevent the achievement of good performance. Overall, this approach still appears promising, but our results indicate that large low latency networks may be needed to make cluster-based virtual shared-memory machines broadly useful as large-scale shared-memory multiprocessors.
Compiler-directed page coloring for multiprocessors
Authors: Bugnion Edouard , Anderson Jennifer M. , Mowry Todd C. , Rosenblum Mendel , Lam Monica S.
Published: October 2004

This paper presents a new technique,
compiler-directed page coloring,
that eliminates conflict misses in multiprocessor applications. It enables applications to make better use of the increased aggregate cache size available in a multiprocessor. This technique uses the compiler's knowledge of the access patterns of the parallelized applications to direct the operating system's virtual memory page mapping strategy. We demonstrate that this technique can lead to significant performance improvements over two commonly used page mapping strategies for machines with either direct-mapped or two-way set-associative caches. We also show that it is complementary to latency-hiding techniques such as prefetching.We implemented compiler-directed page coloring in the SUIF parallelizing compiler and on two commercial operating systems. We applied the technique to the SPEC95fp benchmark suite, a representative set of numeric programs. We used the SimOS machine simulator to analyze the applications and isolate their performance bottlenecks. We also validated these results on a real machine, an eight-processor 350MHz Digital AlphaServer. Compiler-directed page coloring leads to significant performance improvements for several applications. Overall, our technique improves the SPEC95fp rating for eight processors by 8% over Digital UNIX's page mapping policy and by 20% over a page coloring, a standard page mapping policy. The SUIF compiler achieves a SPEC95fp ratio of 57.4, the highest ratio to date.
Improving cache performance with balanced tag and data paths
Authors: Peir Jih-Kwon , Hsu Windsor W. , Young Honesty , Ong Shauchi
Published: October 2004

There are two concurrent paths in a typical cache access --- one through the data array and the other through the tag array. The path through the data array drives the selected set out of the array. The path through the tag array determines cache hit/miss and, for set-associative caches, selects the appropriate line from within the selected set. In both direct-mapped and set-associative caches, the path through the tag array is significantly longer than that through the data array. In this paper, we propose a path balancing technique help match the delays of the tag and data paths. The basic idea behind this technique is to employ a separate subset of the tag array to decouple the one-to-one relationship between address tags and cache lines so as to achieve a design that provides higher performance. Performance evaluation using both TPC-C and SPEC92 benchmarks shows that this path balancing technique offers impressive improvements in overall system performance over conventional cache designs. For TPC-C, improvements in the range of 6% to 28% are possible.
Ada in distributed systems
Authors: Paprzycki Marcin , Zalewski Janusz
Published: October 2004

This paper reviews the available literature on the use of Ada in distributed systems. The following issues are discussed in more detail: units of distribution, program partitioning, building configurations, interprogram communication, type checking, and Ada '95 partitions model. Several systems and a few applications are also covered briefly.
Group membership and view synchrony in partitionable asynchronous distributed systems
Authors: Babaoğlu Özalp , Davoli Renzo , Montresor Alberto
Published: October 2004

Transient failures, unknown scheduling strategies and variable loads on the computing and communication resources give rise to an
asynchronous
and
partitionable
characterization for practical distributed systems with large geographic extent. We consider the group membership problem in partitionable asynchronous systems and give a formal specification that guarantees liveness and prevents capricious view splitting. Our work is based on the notion of
reachability
as an appropriate characterization of failures in partitionable systems in that it subsumes both process crashes and communication failures. The group membership problem is formulated in the context of
view synchrony
that includes a reliable multicast service for communication within the group. Our specification is modular and includes properties governing group membership separately from those governing reliable multicasts. It can be taken either partially for defining a group membership service alone, or taken as a whole for defining view synchrony.