bluuebunny/crossref_metadata_2025 huggingface dataset:
Dynamic tracking of page miss ratio curve for memory management
Authors: Zhou Pin , Pandey Vivek , Sundaresan Jagadeesan , Raghuraman Anand , Zhou Yuanyuan , Kumar Sanjeev
Published: January 2005

Memory can be efficiently utilized if the dynamic memory demands of applications can be determined and analyzed at run-time. The page miss ratio curve(MRC), i.e. page miss rate vs. memory size curve, is a good performance-directed metric to serve this purpose. However, dynamically tracking MRC at run time is challenging in systems with virtual memory because not every memory reference passes through the operating system (OS).This paper proposes two methods to dynamically track MRC of applications at run time. The first method is using a hardware MRC monitor that can track MRC at fine time granularity. Our simulation results show that this monitor has negligible performance and energy overheads. The second method is an OS-only implementation that can track MRC at coarse time granularity. Our implementation results on
Linux
show that it adds only 7--10% overhead.We have also used the dynamic MRC to guide both memory allocation for multiprogramming systems and memory energy management. Our
real system
experiments on Linux with applications including Apache Web Server show that the MRC-directed memory allocation can speed up the applications' execution/response time by up to a factor of 5.86 and reduce the number of page faults by up to 63.1%. Our execution-driven simulation results with SPEC2000 benchmarks show that the MRC-directed memory energy management can improve the Energy * Delay metric by 27--58% over previously proposed static and dynamic schemes.
Formal online methods for voltage/frequency control in multiple clock domain microprocessors
Authors: Wu Qiang , Juang Philo , Martonosi Margaret , Clark Douglas W.
Published: January 2005

Multiple Clock Domain (MCD) processors are a promising future alternative to today's fully synchronous designs. Dynamic Voltage and Frequency Scaling (DVFS) in an MCD processor has the extra flexibility to adjust the voltage and frequency in each domain independently. Most existing DVFS approaches are profile-based offline schemes which are mainly suitable for applications whose execution char-acteristics are constrained and repeatable. While some work has been published about online DVFS schemes, the prior approaches are typically heuristic-based. In this paper, we present an effective online DVFS scheme for an MCD processor which takes a formal analytic approach, is driven by dynamic workloads, and is suitable for all applications. In our approach, we model an MCD processor as a queue-domain network and the online DVFS as a feedback control problem with issue queue occupancies as feedback signals. A dynamic stochastic queuing model is first proposed and linearized through an accu-rate linearization technique. A controller is then designed and verified by stability analysis. Finally we evaluate our DVFS scheme through a cycle-accurate simulation with a broad set of applications selected from MediaBench and SPEC2000 benchmark suites. Compared to the best-known prior approach, which is heuristic-based, the proposed online DVFS scheme is substantially more effective due to its automatic regulation ability. For example, we have achieved a 2-3 fold increase in efficiency in terms of energy-delay product improvement. In addition, our control theoretic technique is more resilient, requires less tuning effort, and has better scalability as compared to prior online DVFS schemes.We believe that the techniques and methodology described in this paper can be generalized for energy control in processors other than MCD, such as tiled stream processors.
Spatial computation
Authors: Budiu Mihai , Venkataramani Girish , Chelcea Tiberiu , Goldstein Seth Copen
Published: January 2005

This paper describes a computer architecture,
Spatial Computation
(SC), which is based on the translation of high-level language programs directly into hardware structures. SC program implementations are completely distributed, with no centralized control. SC circuits are optimized for
wires
at the expense of computation units.In this paper we investigate a particular implementation of SC: ASH (Application-Specific Hardware). Under the assumption that computation is cheaper than communication, ASH replicates computation units to simplify interconnect, building a system which uses very simple, completely dedicated communication channels. As a consequence, communication on the datapath never requires arbitration; the only arbitration required is for accessing memory. ASH relies on very simple hardware primitives, using no associative structures, no multiported register files, no scheduling logic, no broadcast, and no clocks. As a consequence, ASH hardware is fast and extremely power efficient.In this work we demonstrate three features of ASH: (1) that such architectures can be built by automatic compilation of C programs; (2) that distributed computation is in some respects fundamentally different from monolithic superscalar processors; and (3) that ASIC implementations of ASH use three orders of magnitude less energy compared to high-end superscalar processors, while being on average only 33% slower in performance (3.5x worst-case).
An ultra low-power processor for sensor networks
Authors: Ekanayake Virantha , Kelly Clinton , Manohar Rajit
Published: January 2005

We present a novel processor architecture designed specifically for use in low-power wireless sensor-network nodes. Our sensor network asynchronous processor (SNAP/LE) is based on an asynchronous data-driven 16-bit RISC core with an extremely low-power idle state, and a wakeup response latency on the order of tens of nanoseconds. The processor instruction set is optimized for sensor-network applications, with support for event scheduling, pseudo-random number generation, bitfield operations, and radio/sensor interfaces. SNAP/LE has a hardware event queue and event coprocessors, which allow the processor to avoid the overhead of operating system software (such as task schedulers and external interrupt servicing), while still providing a straightforward programming interface to the designer. The processor can meet performance levels required for data monitoring applications while executing instructions with tens of picojoules of energy.We evaluate the energy consumption of SNAP/LE with several applications representative of the workload found in data-gathering wireless sensor networks. We compare our architecture and software against existing platforms for sensor networks, quantifying both the software and hardware benefits of our approach.
Continual flow pipelines
Authors: Srinivasan Srikanth T. , Rajwar Ravi , Akkary Haitham , Gandhi Amit , Upton Mike
Published: January 2005

Increased integration in the form of multiple processor cores on a single die, relatively constant die sizes, shrinking power envelopes, and emerging applications create a new challenge for processor architects. How to build a processor that provides high single-thread performance and enables multiple of these to be placed on the same die for high throughput while dynamically adapting for future applications? Conventional approaches for high single-thread performance rely on large and complex cores to sustain a large instruction window for memory tolerance, making them unsuitable for multi-core chips. We present
Continual Flow Pipelines
(CFP) as a new non-blocking processor pipeline architecture that achieves the performance of a large instruction window without requiring cycle-critical structures such as the scheduler and register file to be large. We show that to achieve benefits of a large instruction window, inefficiencies in management of both the scheduler and register file must be addressed, and we propose a unified solution. The non-blocking property of CFP keeps key processor structures affecting cycle time and power (scheduler, register file), and die size (second level cache) small. The memory latency-tolerant CFP core allows multiple cores on a single die while outperforming current processor cores for single-thread applications.
Scalable selective re-execution for EDGE architectures
Authors: Desikan Rajagopalan , Sethumadhavan Simha , Burger Doug , Keckler Stephen W.
Published: January 2005

Pipeline flushes are becoming increasingly expensive in modern microprocessors with large instruction windows and deep pipelines. Selective re-execution is a technique that can reduce the penalty of mis-speculations by re-executing only instructions affected by the mis-speculation, instead of all instructions. In this paper we introduce a new selective re-execution mechanism that exploits the properties of a dataflow-like Explicit Data Graph Execution (EDGE) architecture to support efficient mis-speculation recovery, while scaling to window sizes of thousands of instructions with high performance. This distributed selective re-execution (DSRE) protocol permits multiple speculative waves of computation to be traversing a dataflow graph simultaneously, with a commit wave propagating behind them to ensure correct execution. We evaluate one application of this protocol to provide efficient recovery for load-store dependence speculation. Unlike traditional dataflow architectures which resorted to single-assignment memory semantics, the DSRE protocol combines dataflow execution with speculation to enable high performance
and
conventional sequential memory semantics. Our experiments show that the DSRE protocol results in an average 17% speedup over the best dependence predictor proposed to date, and obtains 82% of the performance possible with a perfect oracle directing the issue of loads.
Heat-and-run
Authors: Gomaa Mohamed , Powell Michael D. , Vijaykumar T. N.
Published: January 2005

Power density in high-performance processors continues to increase with technology generations as scaling of current, clock speed, and device density outpaces the downscaling of supply voltage and thermal ability of packages to dissipate heat. Power density is characterized by localized chip hot spots that can reach critical temperatures and cause failure. Previous architectural approaches to power density have used global clock gating, fetch toggling, dynamic frequency scaling, or resource duplication to either prevent heating or relieve overheated resources in a superscalar processor. Previous approaches also evaluate design technologies where power density is not a major problem and most applications do not overheat the processor. Future processors, however, are likely to be chip multiprocessors (CMPs) with simultaneously-multithreaded (SMT) cores. SMT CMPs pose unique challenges and opportunities for power density. SMT and CMP increase throughput and thus on-chip heat, but also provide natural granularities for managing power-density. This paper is the first work to leverage SMT and CMP to address power density. We propose heat-and-run SMT thread assignment to increase processor-resource utilization before cooling becomes necessary by co-scheduling threads that use complimentary resources. We propose heat-and-run CMP thread migration to migrate threads away from overheated cores and assign them to free SMT contexts on alternate cores, leveraging availability of SMT contexts on alternate CMP cores to maintain throughput while allowing overheated cores to cool. We show that our proposal has an average of 9% and up to 34% higher throughput than a previous superscalar technique running the same number of threads.
Feature-based surface parameterization and texture mapping
Authors: Zhang Eugene , Mischaikow Konstantin , Turk Greg
Published: January 2005

Surface parameterization is necessary for many graphics tasks: texture-preserving simplification, remeshing, surface painting, and precomputation of solid textures. The stretch caused by a given parameterization determines the sampling rate on the surface. In this article, we present an automatic parameterization method for segmenting a surface into patches that are then flattened with little stretch.

Many objects consist of regions of relatively simple shapes, each of which has a natural parameterization. Based on this observation, we describe a three-stage feature-based patch creation method for manifold surfaces. The first two stages, genus reduction and feature identification, are performed with the help of distance-based surface functions. In the last stage, we create one or two patches for each feature region based on a covariance matrix of the feature's surface points.

To reduce stretch during patch unfolding, we notice that stretch is a 2 × 2 tensor, which in ideal situations is the identity. Therefore, we use the Green-Lagrange tensor to measure and to guide the optimization process. Furthermore, we allow the boundary vertices of a patch to be optimized by adding scaffold triangles. We demonstrate our feature-based patch creation and patch unfolding methods for several textured models.

Finally, to evaluate the quality of a given parameterization, we describe an image-based error measure that takes into account stretch, seams, smoothness, packing efficiency, and surface visibility.
Simulating the dynamics of auroral phenomena
Authors: Baranoski Gladimir V. G. , Wan Justin , Rokne Jon G. , Bell Ian
Published: January 2005

Simulating natural phenomena has always been a focal point for computer graphics research. Its importance goes beyond the production of appealing presentations, since research in this area can contribute to the scientific understanding of complex natural processes. The natural phenomena, known as the Aurora Borealis and Aurora Australis, are geomagnetic phenomena of impressive visual characteristics and remarkable scientific interest. Aurorae present a complex behavior that arises from interactions between plasma (hot, ionized gases composed of ions, electrons, and neutral atoms) and Earth's electromagnetic fields. Previous work on the visual simulation of auroral phenomena have focused on static physical models of their shape, modeled from primitives, like sine waves. In this article, we focus on the dynamic behavior of the aurora, and we present a physically-based model to perform 3D visual simulations. The model takes into account the physical parameters and processes directly associated with plasma flow, and can be extended to simulate the dynamics of other plasma phenomena as well as astrophysical phenomena. The partial differential equations associated with these processes are solved using a complete multigrid implementation of the electromagnetic interactions, leading to a simulation of the shape and motion of the auroral displays. In order to illustrate the applicability of our model, we provide simulation sequences rendered using a distributed forward mapping approach.
On the optimality of spectral compression of mesh data
Authors: Ben-Chen Mirela , Gotsman Craig
Published: January 2005

Spectral compression of the geometry of triangle meshes achieves good results in practice, but there has been little or no theoretical support for the optimality of this compression. We show that, for certain classes of geometric mesh models, spectral decomposition using the eigenvectors of the symmetric Laplacian of the connectivity graph is equivalent to principal component analysis on that class, when equipped with a natural probability distribution. Our proof treats connected one-and two-dimensional meshes with fixed convex boundaries, and is based on an asymptotic approximation of the probability distribution in the two-dimensional case. The key component of the proof is that the Laplacian is identical, up to a constant factor, to the inverse covariance matrix of the distribution of valid mesh geometries. Hence, spectral compression is optimal, in the mean square error sense, for these classes of meshes under some natural assumptions on their distribution.
Stable but nondissipative water
Authors: Song Oh-Young , Shin Hyuncheol , Ko Hyeong-Seok
Published: January 2005

This article presents a physically-based technique for simulating water. This work is motivated by the "stable fluids" method, developed by Stam [1999], to handle gaseous fluids. We extend this technique to water, which calls for the development of methods for modeling multiphase fluids and suppressing dissipation. We construct a multiphase fluid formulation by combining the Navier--Stokes equations with the level set method. By adopting constrained interpolation profile (CIP)-based advection, we reduce the numerical dissipation and diffusion significantly. We further reduce the dissipation by converting potentially dissipative cells into droplets or bubbles that undergo Lagrangian motion. Due to the multiphase formulation, the proposed method properly simulates the interaction of water with surrounding air, instead of simulating water in a void space. Moreover, the introduction of the nondissipative technique means that, in contrast to previous methods, the simulated water does not unnecessarily lose mass, and its motion is not damped to an unphysical extent. Experiments showed that the proposed method is stable and runs fast. It is demonstrated that two-dimensional simulation runs in real-time.
Controllable smoke animation with guiding objects
Authors: Shi Lin , Yu Yizhou
Published: January 2005

This article addresses the problem of controlling the density and dynamics of smoke (a gas phenomenon) so that the synthetic appearance of the smoke (gas) resembles a still or moving object. Both the smoke region and the target object are represented as implicit functions. As a part of the target implicit function, a shape transformation is generated between an initial smoke region and the target object. In order to match the smoke surface with the target surface, we impose carefully designed velocity constraints on the smoke boundary during a dynamic fluid simulation. The velocity constraints are derived from an iterative functional minimization procedure for shape matching. The dynamics of the smoke is formulated using a novel compressible fluid model which can effectively absorb the discontinuities in the velocity field caused by imposed velocity constraints while reproducing realistic smoke appearances. As a result, a smoke region can evolve into a regular object and follow the motion of the object, while maintaining its smoke appearance.
Designing BGP-based outbound traffic engineering techniques for stub ASes
Authors: Uhlig Steve , Bonaventure Olivier
Published: January 2005

Today, most multi-connected autonomous systems (AS) need to control the flow of their interdomain traffic for both performance and economical reasons. This is usually done by manually tweaking the BGP configurations of the routers on an error-prone trial-and-error basis. In this paper, we demonstrate that designing systematic BGP-based traffic engineering techniques for stub ASes are possible. Our approach to solve this traffic engineering problem is to allow the network operator to define objective functions on the interdomain traffic. Those objective functions are used by an optimization box placed inside the AS that controls the interdomain traffic by tuning the iBGP messages distributed inside the AS. We show that the utilization of an efficient evolutionary algorithm allows to both optimize the objective function and limit the number of iBGP messages. By keeping a lifetime on the tweaked routes, we also show that providing stability to the interdomain path followed by the traffic is possible. We evaluate the performance of solution based on traffic traces from two stub ASes of different sizes. Our simulations show that the interdomain traffic can be efficiently engineered by using not more than a few iBGP advertisements per minute.Our contribution in this paper is to demonstrate that by carefully thinking the design of the interdomain traffic engineering technique, stub ASes can engineer their outbound traffic over relatively short timescales, by exclusively tweaking their BGP routes, and with a minimal burden on BGP. Systematic BGP-based traffic engineering for stub ASes is thus possible at a very limited cost in terms of iBGP messages.
Quantum networks
Authors: Curcic Tatjana , Filipkowski Mark E. , Chtchelkanova Almadena , D'Ambrosio Philip A. , Wolf Stuart A. , Foster Michael , Cochran Douglas
Published: January 2005

As classical information technology approaches limits of size and functionality, practitioners are searching for new paradigms for the distribution and processing of information. Our goal in this Introduction is to provide a broad view of the beginning of a new era in information technology, an era of quantum information, where previously underutilized quantum effects, such as quantum superposition and entanglement, are employed as resources for information encoding and processing. The ability to distribute these new resources and connect distant quantum systems will be critical. We present an overview of network implications for quantum communication applications, and for quantum computing. This overview is a selection of several illustrative examples, to serve as motivation for the network research community to bring its expertise to the development of quantum information technologies.
Quantum-noise
Authors: Corndorf Eric , Liang Chuang , Kanter Gregory S. , Kumar Prem , Yuen Horace P.
Published: January 2005

We demonstrate high data-rate quantum-noise{protected data encryption through optical fibers using coherent states of light. Specifically, we demonstrate 650Mbps data encryption through a 10Gbps data-bearing, in-line amplified 200km-long line. In our protocol, legitimate users (who share a short secret-key) communicate using an M-ry signal set while an attacker (who does not share the secret-key) is forced to contend with the fundamental and irreducible quantum-measurement noise of coherent states. Implementations of our protocol using both polarization-encoded signal sets as well as polarization-insensitive phase-keyed signal sets are experimentally and theoretically evaluated. Different from the performance criteria of the cryptographic objective of key generation (quantum key generation), the performance criteria of data encryption are established and carefully considered.
A real options framework to value network, protocol, and service architecture
Authors: Gaynor Mark , Bradner Scott
Published: January 2005

This paper proposes a real options framework for evaluating architectural choices and the economic value of these alternative choices of networks, protocols, and services. Using proven financial techniques of real options, our model explores the value of distributed architecture compared to the benefits of centralized control. Voice and email case studies that agree with our theory and model are presented. We apply our model to illustrate the value of end-to-end structure, why SIP-based VoIP is winning, and the value of open garden service business models allowing third parties to provide network services/applications. This work illustrates the potential of real options to help quantify the economic value of network, protocol, and service architectures.
Surfing the net for software engineering notes
Authors: Doernhoefer Mark
Published: January 2005

Building real-time applications can be one of the most difficult jobs facing today's software engineers. With all the talk about Web services and Web based applications we sometimes forget that there is a large community of practice engaged in the construction of hard real-time systems. Real-time software engineering has been around for several decades. Typical real-time applications can be found in the areas of communications, avionics, process control, and other specialized applications such as signaling and switching systems.
ICSE 2004 workshop on architecting dependable systems
Authors: de Lemos Rogério , Gacek Cristina , Romanovsky Alexander
Published: January 2005

This summary gives a brief overview of a one-day Workshop on Architecting Dependable Systems (WADS) held in conjunction with ICSE 2004. It was organised as a twin workshop with a Workshop held in conjunction with the International Conference on Dependable Systems and Network (DSN 2004).
Report on MSR 2004
Authors: Hassan Ahmed E. , Holt Richard C. , Mockus Audris
Published: January 2005

A one-day workshop was held on the topic of mining software repositories at ICSE 2004 in Edinburgh, Scotland. The workshop brought together researchers and practitioners in order to consider methods that use data stored in software repositories (such as source control systems, defect tracking systems, and archived project communications) to further understanding of software development practices. We divided submissions into six sessions, each devoted to a particular topic: 1) Infrastructure and Extraction, 2) Integration and Presentation, 3) System Understanding and Change Patterns, 4) Defect Analysis, 5) Process and Community Analysis, and 6) Software Reuse. To maximize interaction and discussion, we limited each session to a survey of the topic area, followed by the presentation of one or two papers, then an open discussion. We also allocated a demo hour to give interested parties the opportunity to learn more about other accepted papers.This report includes an overview of the presentations made during these sessions and a summary of the issues raised throughout the workshop.
Software dissimilarity debate revisited
Authors: Bhansali P. V.
Published: January 2005

This paper highlights the controversy surrounding the use of dissimilarity for improved safety. It compares dissimilarity at the system level versus software level and uses examples from the commercial and military safety-critical standards to highlight this controversy. It proposes a solution by identifying those systems which can find dissimilarity beneficial and those that may find dissimilarity detrimental regardless of whether dissimilarity is implemented at the system level or at the software level. Practical examples are cited to highlight how these concepts can be used in the real-world.
Testing web applications focusing on their specialties
Authors: Xu Lei , Xu Baowen , Jiang Jixiang
Published: January 2005

Nowadays, Web applications are very prevalent around the world, and it becomes more and more important to ensure their qualities by testing. However, due to the special characters of Web applications, traditional testing methods are not suitable for Web testing in many aspects. So based on the related work by now, this paper presents our research work in such areas as the Web application modeling, the test case generation, the detailed testing methods and techniques, the testing executing process, and the testing measurements. And based on the rules of software engineering, these processes are the necessary parts of the whole testing. Our methods focus on such specialties as numerous users, distributed structures, dynamic and interactive functions of Web applications and the improvements for the testing efficiency.
Spatial gossip and resource location protocols
Authors: Kempe David , Kleinberg Jon , Demers Alan
Published: January 2005

The dynamic behavior of a network in which information is changing continuously over time requires robust and efficient mechanisms for keeping nodes updated about new information.
Gossip protocols
are mechanisms for this task in which nodes communicate with one another according to some underlying deterministic or randomized algorithm, exchanging information in each communication step. In a variety of contexts, the use of randomization to propagate information has been found to provide better reliability and scalability than more regimented deterministic approaches.In many settings, such as a cluster of distributed computing hosts, new information is generated at individual nodes, and is most "interesting" to nodes that are nearby. Thus, we propose
distance-based propagation bounds
as a performance measure for gossip mechanisms: a node at distance
d
from the origin of a new piece of information should be able to learn about this information with a delay that grows slowly with
d
, and is
independent
of the size of the network.For nodes arranged with uniform density in Euclidean space, we present natural gossip mechanisms, called
spatial gossip
, that satisfy such a guarantee: new information is spread to nodes at distance
d
, with high probability, in
O
(log
1 + ε
d
) time steps. Such a bound combines the desirable qualitative features of
uniform gossip
, in which information is spread with a delay that is logarithmic in the full network size, and
deterministic flooding
, in which information is spread with a delay that is linear in the distance and independent of the network size. Our mechanisms and their analysis resolve a conjecture of Demers et al. [1987].We further show an application of our gossip mechanisms to a basic
resource location problem
, in which nodes seek to rapidly learn the location of the nearest copy of a
resource
in a network. This problem, which is of considerable practical importance, can be solved by a very simple protocol using Spatial Gossip, whereas we can show that no protocol built on top of uniform gossip can inform nodes of their approximately nearest resource within poly-logarithmic time. The analysis relies on an additional useful property of spatial gossip, namely that information travels from its source to sinks along short paths not visiting points of the network far from the two nodes.
A new approach to dynamic all pairs shortest paths
Authors: Demetrescu Camil , Italiano Giuseppe F.
Published: January 2005

We study novel combinatorial properties of graphs that allow us to devise a completely new approach to dynamic all pairs shortest paths problems. Our approach yields a fully dynamic algorithm for general directed graphs with non-negative real-valued edge weights that supports any sequence of operations in
O
(
n
2
log
3
n
) amortized time per update and unit worst-case time per distance query, where
n
is the number of vertices. We can also report shortest paths in optimal worst-case time. These bounds improve substantially over previous results and solve a long-standing open problem. Our algorithm is deterministic, uses simple data structures, and appears to be very fast in practice.
Compact oracles for reachability and approximate distances in planar digraphs
Authors: Thorup Mikkel
Published: January 2005

It is shown that a planar digraph can be preprocessed in near-linear time, producing a near-linear space oracle that can answer reachability queries in constant time. The oracle can be distributed as an
O
(log
n
) space label for each vertex and then we can determine if one vertex can reach another considering their two labels only.The approach generalizes to give a near-linear space approximate distances oracle for a weighted planar digraph. With weights drawn from {0, …,
N
}, it approximates distances within a factor (1 + ε) in
O
(log log (
nN
) + 1/ε) time. Our scheme can be extended to find and route along correspondingly short dipaths.
Fast monte-carlo algorithms for finding low-rank approximations
Authors: Frieze Alan , Kannan Ravi , Vempala Santosh
Published: January 2005

We consider the problem of approximating a given
m
×
n
matrix
A
by another matrix of specified rank
k
, which is smaller than
m
and
n
. The Singular Value Decomposition (SVD) can be used to find the "best" such approximation. However, it takes time polynomial in
m, n
which is prohibitive for some modern applications. In this article, we develop an algorithm that is qualitatively faster, provided we may sample the entries of the matrix in accordance with a natural probability distribution. In many applications, such sampling can be done efficiently. Our main result is a randomized algorithm to find
the description of
a matrix

D

*
of rank at most
k
so that holds with probability at least 1 − δ (where |·|

F

is the Frobenius norm). The algorithm takes time polynomial in
k
,1/ϵ, log(1/δ) only and is
independent of m and n
. In particular, this implies that in constant time, it can be determined if a given matrix of arbitrary size has a good low-rank approximation.
The Big Programming Languages Issue
Authors: Grossman Edward
Published: January 2005

As I write this month’s Editor’s Note, I sit upon the eve of the 2004 Presidential election, and by all counts it’s anybody’s game. Of course, by the time this reaches you the outcome (hopefully) will be clear. Now I’m not going to here, on the pages of ACM Queue, a magazine dedicated to practical technology issues for technologists, sound off about my political leanings.
Kode Vicious: The Return
Authors: Neville-Neil George
Published: January 2005

Dear KV, Whenever my team reviews my code, they always complain that I don’t check for return values from system calls. I can see having to check a regular function call, because I don’t trust my co-workers, but system calls are written by people who know what they’re doing--and, besides, if a system call fails, there isn’t much I can do to recover. Why bother?
Linguae Francae
Authors: Kelly-Bootle Stan
Published: January 2005

Many linguists are still busy trying to reconstruct the single ur-language presumed to have evolved over untold millennia into the thousands of human tongues - alive and dead, spoken and written - that have since been catalogued and analyzed. The amazing variety and complexity of known languages and dialects seems, at first parse, to gainsay such a singular seed.
Fuzzy Boundaries: Objects, Components, and Web Services
Authors: Sessions Roger
Published: January 2005

If you are an object-oriented programmer, you will understand the code snippet, even if you are not familiar with the language (C#, not that it matters). You will not be surprised to learn that this program will print out the following line to the console: woof.
Self-Healing in Modern Operating Systems
Authors: Shapiro Michael W.
Published: January 2005

Driving the stretch of Route 101 that connects San Francisco to Menlo Park each day, billboard faces smilingly reassure me that all is well in computerdom in 2004. Networks and servers, they tell me, can self-defend, self-diagnose, self-heal, and even have enough computing power left over from all this introspection to perform their owner-assigned tasks.
Evaluating end-user training programs
Authors: Mahapatra RadhaKanta , Lai Vincent S.
Published: January 2005

With some planning and coordination, organizations can implement an evaluation scheme to get the most out of their computer skills training programs.
Timeliness of investor relations data at corporate web sites
Authors: Ettredge Michael , Jr. John Gerdes
Published: January 2005

Online data for investors is often stale, even when of high quality. How can this situation be improved?
Let your fingers do the talking
Authors: McGinity Meg
Published: January 2005

Biometrics is pointing its way into everyday applications. But figuring out how it fits into telecom and wireless services, never mind society, might just get downright touchy.
Minority-minority and minority-majority technology transfer
Authors: Patterson David A.
Published: January 2005

Finding technology solutions to help those in need can often lead to welcomed answers for all if we look at the big picture.
Working with young children as technology design partners
Authors: Guha Mona Leigh , Druin Allison , Chipman Gene , Fails Jerry Alan , Simms Sante , Farber Allison
Published: January 2005

A case study illustrates how even young children can contribute to the technology design process.
Ubi-learning integrates indoor and outdoor experiences
Authors: Rogers Yvonne , Price Sara , Randell Cliff , Fraser Danae Stanton , Weal Mark , Fitzpatrick Geraldine
Published: January 2005

Digital augmentation dissolves many of the physical barriers to learning by offering tools to integrate data and discoveries that travel with students as they explore new terrain.
Story creation in virtual game worlds
Authors: Robertson Judy , Good Judith
Published: January 2005

Allowing young people to create computer games they will ultimately want to play not only offers key educational benefits but builds self-esteem and teamwork skills.
Assessing the value of IS journals
Authors: Barnes Stuart J.
Published: January 2005

Using journal citation reports to determine the influence and impact of a variety of journals publishing IS research.
An adaptive
k
-nearest neighbor text categorization strategy
Authors: Baoli Li , Qin Lu , Shiwen Yu
Published: January 2005

k
is the most important parameter in a text categorization system based on the
k
-nearest neighbor algorithm (
k
NN). To classify a new document, the
k
-nearest documents in the training set are determined first. The prediction of categories for this document can then be made according to the category distribution among the
k
nearest neighbors. Generally speaking, the class distribution in a training set is not even; some classes may have more samples than others. The system's performance is very sensitive to the choice of the parameter
k
. And it is very likely that a fixed
k
value will result in a bias for large categories, and will not make full use of the information in the training set. To deal with these problems, an improved kNN strategy, in which different numbers of nearest neighbors for different categories are used instead of a fixed number across all categories, is proposed in this article. More samples (nearest neighbors) will be used to decide whether a test document should be classified in a category that has more samples in the training set. The numbers of nearest neighbors selected for different categories are adaptive to their sample size in the training set. Experiments on two different datasets show that our methods are less sensitive to the parameter
k
than the traditional ones, and can properly classify documents belonging to smaller classes with a large
k
. The strategy is especially applicable and promising for cases where estimating the parameter
k
via cross-validation is not possible and the class distribution of a training set is skewed.
Algorithm 839
Authors: Kirby Robert C.
Published: January 2005

Much of finite element computation is constrained by the difficulty of evaluating high-order nodal basis functions. While most codes rely on explicit formulae for these basis functions, we present a new approach that allows us to construct a general class of finite element basis functions from orthonormal polynomials and evaluate and differentiate them at any points. This approach relies on fundamental ideas from linear algebra and is implemented in Python using several object-oriented and functional programming techniques.
An operational semantics for Scheme
Authors: Ramsdell John D.
Published: January 2005

In the informal description of Scheme, the order of evaluating the operands and the operator of each application is unspecified. This paper presents an operational semantics for Scheme which faithfully reflects this fact. Furthermore, when the semantics is restricted so as to assume there is one unspecified order used throughout a program, the semantics is shown to be sound with respect to the denotational semantics of Scheme.
The buried binding and dead binding problems of Lisp 1.5
Authors: Baker Henry G.
Published: January 2005

Lisp has become the language of choice for many applications such as artificial intelligence programs or symbol manipulation. The original implementation of Lisp 1.5 was a concise, elegant statement of the semantics of the language. Although production Lisp systems have undergone significant development and evolution since Lisp 1.5, including the development of sophisticated compilers, there have been few significant theoretical improvements in the implementations of these systems. Most improvements, such as arrays or shallow-binding, have been made more for the sake of speed than for the sake of storage. A notable exception to this is the technique of tail recursion, which can save more than just stack space.We believe that more can be done to reduce the storage requirements of Lisp programs. Although in many instances, the Lisp programmer can reduce the storage requirements of his program by deleting unneeded pointers as soon as possible, there is nothing he can do about systematic inefficiencies of the Lisp interpreter. This paper addresses itself to two sources of inefficiency in Lisp's variable binding mechanism--one of which is easy to detect---which prevent storage from being garbage collected long after its last reference. Implementations of Lisp which eliminate these situations should result in more economical execution for almost all Lisp programs which use a lot of storage, due to a lighter marking load on the garbage collector.
A package for handling units of measure in Lisp
Authors: Cunis Roman
Published: January 2005

The ability to handle units of measure in a programming environment together with numerical quantities in scientific and engineering programs helps greatly in achieving computational safety as well as code and data readability. It allows for dimensional analysis, thus safeguarding against erroneous combination of values of different dimensionality, e.g. adding distances to masses, or against scaling errors, e.g. assigning distances measured in inch to variables supposed to hold centimeters. Associating values and variables with units of measure explicitly clarifies code and data and---given a clever compiler---allows for the above-mentioned dimensional analysis to be performed at compile time. If extended to input and output of user data, it might free the user from the burden to perform proper scaling himself when entering data conforming to program-defined units of measure. And it might allow for easy customization of output in order to present computational results to users familiar with different sets of units of measure, e.g. British and American use of units versus metric units.
Using the new common Lisp pretty printer
Authors: Waters Richard C.
Published: January 2005

Although not part of the initial definition of the language, pretty printing has been an important feature of Lisp programming environments for twenty years or more [1]. By the time Common Lisp was being defined, the importance of pretty printing was clear enough that pretty printing was made a formal part of the language [2]. However, little was done beyond recognizing the least common denominator of the pretty printing facilities available at the time---[2] specifies how pretty printing can be turned on and off, but says very little else. In particular, no provision was made for allowing the user to control what the pretty printer does.
Performance in contention bus local network interconnection
Authors: Watson W. B.
Published: January 2005

Various levels of protocols of local area broadcast networks interact. These interactions degrade network performance and have been studied using descrete event simulation techniques. Some of the design aspects that have a marked effect on network performance are briefly outlined and the relevant literature indicated.
The effect of satellite lines on the ARPANET protocols
Authors: Williams Graeme
Published: January 2005

This paper is based on a test that was run on a small network which included a high speed satellite line. The network was running with the standard ARPANET protocols. We will be interested in the link protocol, which ensures reliable transmission from one node to the next, and the end-to-end protocol, which ensures reliable transmission from the source node to the destination node. Only some details of these protocols will be relevant here. We will not be concerned with higher level protocols, such as the host-host protocol, Telnet or FTP.
A communication concept for protocol models
Authors: Bauerfeld Wulfdieter L.
Published: January 2005

A concept is introduced for the communication within hierarchically ordered distributed systems like computer network protocols. Characterstrings common for output and input instructions are sufficient to describe a broadcast communication via an unbuffered send. The broadcast can be restricted to clusters of processes to express the physical links in a network. Any hierarchical order is not described in process types but in messages which can be encoded or decoded.
Networks and flow control
Authors: Dhas C. Retna
Published: January 2005

The clear advantages inherent in dynamic sharing of resources has accelerated the development of distributed processing. The number of networks which provide resource sharing have increased steadily from the early years of ARPA network. As the number of users sharing the resources increases, there is a potential danger for degradation of services, if the demand for the resources is greater than the available resources. The maximum traffic that can be carried by a network depends on the finite network resources such as link bandwidth and storage buffers. An uncontrolled flow of traffic results in service degradation and deadlock if the traffic allowed into the network exceeds the capacity of the network.
Rules for synthesizing correct communication protocols
Authors: Sidhu Deepinder P.
Published: January 2005

An approach to communication protocols synthesis is proposed which permits the development of general (FIFO and non-FIFO channels), N-party (N>=2) protocols with the following properties: completeness, deadlock freeness, livelock or tempo-blocking freeness, termination or cyclic behavior, liveness, boundedness and absence of non-executable interactions.
Comments on "congestion control in TCP/IP internetworks"
Authors: Grossman Daniel B.
Published: January 2005

The article "Congestion control in IP/TCP Internetworks" by John Nagle is an excellent illustration of problems inherent in Arpanet and Milnet technology. The article describes a series of congestion related performance difficulties in a TCP/IP network at Ford Aerospace, and suggested some "cures".What in fact the article describes is what appear to be adequate "band-aids" for the basic inadequacies of Arpanet technology. However, it fails to address the root causes of the performance difficulties that Mr. Nagle discusses. It is suggested that all of these problems result from an uncritical adherence to the Arpanet paradigm, without regard to the research and standardization work of the past 15 years.
Internet nuggets
Authors: Thorson Mark
Published: January 2005

This column consists of selected traffic from the comp.arch newsgroup, a forum for discussion of computer architecture on the Internet--an international computer network.As always, the opinions expressed in this column are the personal views of the authors, and do not necessarily represent the institutions to which they are affiliated.Text which sets the context of a message appears underlined or in italics; this is usually text the author has quoted from earlier messages. The code-like expressions below the authors' names are their addresses on Internet.
The ISO internetwork protocol standard
Authors: Piscitello David M.
Published: January 2005

A great deal has already been written about the development by the International Organization for Standardization of a Reference Model for Open Systems Interconnection. The Reference Model provides a framework for the development of standards for the interconnection of computer and terminal equipment. It describes an architecture wherein functions ascribed to providing communications are separated into a hierarchy of seven layers. Each layer provides services to the next higher layer, utilizing the services provided by subordinate layers in order to achieve that end. At each layer, protocols are employed to convey information between peer layer entities in individual systems. When in compliance with a suite of standard protocols prescribed for OSI, systems are considered to be "open".
Design of an authentication service
Authors: Chung Anthony , Sherman Richard
Published: January 2005

The purpose of this paper is to provide a design example of an authentication service as a means of privacy in information exchange between presentation entities. The service is contained in the session layer and interfaces with the lower layer transport service and upper layer presentation entities. The transport layer service interface is defined to be compatible with the DoD IP/TCP standard and the NBS proposed ISO transport standard.