bluuebunny/crossref_metadata_2025 huggingface dataset:
Implicitly-multithreaded processors
Authors: Park Il , Falsafi Babak , Vijaykumar T. N.
Published: July 2004

This paper proposes the Implicitly-MultiThreaded (IMT) architecture to execute compiler-specified speculative threads on to a modified Simultaneous Multithreading pipeline. IMT reduces hardware complexity by relying on the compiler to select suitable thread spawning points and orchestrate inter-thread register communication. To enhance IMT's effectiveness, this paper proposes three novel microarchitectural mechanisms: (1) resource- and dependence-based fetch policy to fetch and execute suitable instructions, (2) context multiplexing to improve utilization and map as many threads to a single context as allowed by availability of resources, and (3) early threadinvocation to hide thread start-up overhead by overlapping one thread's invocation with other threads' execution.We use SPEC2K benchmarks and cycle-accurate simulation to show that an microarchitecture-optimized IMT improves performance on average by 24% and at best by 69% over an aggressive superscalar. We also compare IMT to two prior proposals, TME and DMT, for speculative threading on an SMT using hardware-extracted threads. Our best IMT design outperforms a comparable TME and DMT on average by 26% and 38% respectively.
MisSPECulation
Authors: Citron Daniel
Published: July 2004

A majority of the papers published in leading computer architecture conferences use SPEC CPU2000, or its predecessor SPEC CPU95, which has become the de facto standard for measuring processor and/or memory-hierarchy performance. However, in most cases a subset of the suite's benchmarks are simulated. For example: 27 papers were published in ISCA 2002, 16 used SPEC CINT2000, 4 used the whole suite, and only 3 papers explained their omissions.This paper quantifies the extent of this phenomenon in the ISCA, Micro, and HPCA conferences: 173 papers were surveyed, 115 used benchmarks from SPEC CINT, but only 23 used the whole suite. If this current trend continues, by the year 2005 80% of the papers will use the full CINT2000 suite, a year after CPU2004 shall be announced.We claim that results based upon a subset of a benchmark suite are speculative and conflict with Amdahl's Law. The law implies that we must present the speedup of using the proposed technique on the whole suite. Projecting the law (by statistically supplying values for the missing benchmarks) to several published papers reduces promising results to average ones. Speedups are reduced from 1.42 to 1.16 in one case, from 1.43 to 1.13 in another, and from 1.76 to 1.15 in a third.Finally, we have found that the disregard for CFP2000 is unwarranted in papers that explore the data cache domain, the suite displays a higher data cache miss rate than CINT2000, which is used more frequently.
Banked multiported register files for high-frequency superscalar microprocessors
Authors: Tseng Jessica H. , Asanović Krste
Published: July 2004

Multiported register files are a critical component of high-performance superscalar microprocessors. Conventional multiported structures can consume significant power and die area. We examine the designs of banked multiported register files that employ multiple interleaved banks of fewer ported register cells to reduce power and area. Banked register files designs have been shown to provide sufficient bandwidth for a superscalar machine, but previous designs had complex control structures that would likely limit cycle time and add to design complexity. We develop a banked register file with much simpler and faster control logic while only slightly increasing the number of ports per bank. We present area, delay, and energy numbers extracted from layouts of the banked register file. For a four-issue superscalar processor, we show that we can reduce area by a factor of three, access time by 20%, and energy by 40%, while decreasing IPC by less than 5%.
SMARTS
Authors: Wunderlich Roland E. , Wenisch Thomas F. , Falsafi Babak , Hoe James C.
Published: July 2004

Current software-based microarchitecture simulators are many orders of magnitude slower than the hardware they simulate. Hence, most microarchitecture design studies draw their conclusions from drastically truncated benchmark simulations that are often inaccurate and misleading. This paper presents the Sampling Microarchitecture Simulation (SMARTS) framework as an approach to enable fast and accurate performance measurements of full-length benchmarks. SMARTS accelerates simulation by selectively measuring in detail only an appropriate benchmark subset. SMARTS prescribes a statistically sound procedure for configuring a systematic sampling simulation run to achieve a desired quantifiable confidence in estimates.Analysis of 41 of the 45 possible SPEC2K benchmark/input combinations show CPI and energy per instruction (EPI) can be estimated to within ±3% with 99.7% confidence by measuring fewer than 50 million instructions per benchmark. In practice, inaccuracy in microarchitectural state initialization introduces an additional uncertainty which we empirically bound to ∼2% for the tested benchmarks. Our implementation of SMARTS achieves an actual average error of only 0.64% on CPI and 0.59% on EPI for the tested benchmarks, running with average speedups of 35 and 60 over detailed simulation of 8-way and 16-way out-of-order processors, respectively.
GOAL
Authors: Singh Arjun , Dally William J. , Gupta Amit K. , Towles Brian
Published: July 2004

We introduce a load-balanced adaptive routing algorithm for torus networks, GOAL - Globally Oblivious Adaptive Locally - that provides high throughput on adversarial traffic patterns, matching or exceeding fully randomized routing and exceeding the worst-case performance of Chaos [2], RLB [14], and minimal routing [8] by more than 40%. GOAL also preserves locality to provide up to 4.6× the throughput of fully randomized routing [19] on local traffic. GOAL achieves global load balance by randomly choosing the direction to route in each dimension. Local load balance is then achieved by routing in the selected directions adaptively. We compare the throughput, latency, stability and hot-spot performance of GOAL to six previously published routing algorithms on six specific traffic patterns and 1,000 randomly generated permutations.
A pipelined memory architecture for high throughput network processors
Authors: Sherwood Timothy , Varghese George , Calder Brad
Published: July 2004

Designing ASICs for each new generation of backbone routers is a time intensive and fiscally draining process. In this paper we focus on the design of a programmable architecture for backbone routers, based on the manipulation of wide irregular memory words, that can provide a feasible design alternative to custom ASICs. We propose a pipelined memory design that emphasizes worst-case throughput over latency, and co-explore architectural tradeoffs with the design of several important network algorithms. Through this co-exploration, we show that a programmable architecture can efficiently exploit behavior inherent to most common network algorithms to keep up with next generation network speeds.
Detecting global stride locality in value streams
Authors: Zhou Huiyang , Flanagan Jill , Conte Thomas M.
Published: July 2004

Value prediction exploits localities in value streams. Previous research focused on exploiting two types of value localities, computational and context-based, in the local value history, which is the value sequence produced by the same instruction that is being predicted. Besides the local value history, value locality also exists in the global value history, which is the value sequence produced by all dynamic instructions according to their execution order. In this paper, a new type value locality, the computational locality in the global value history is studied. A novel prediction scheme, called the gDiff predictor, is designed to exploit one special and most common case of this computational model, the stridebased computation, in the global value history. Such a scheme provides a general framework to exploit global stride locality in any value stream. Experiments show that there exists very strong stride type of locality in global value sequences. Ideally, the gDiff predictor can achieve 73% prediction accuracy for all value producing instructions without any hybrid scheme, much higher than local stride and local context prediction schemes. However, the capability of realistically exploiting locality in global value history is greatly challenged by the value delay issue, i.e., the correlated value may not be available when the prediction is being made. We study the value delay issue in an out-of-order (OOO) execution pipeline model and propose a new hybrid scheme to maximize the exploitation of the global stride locality. This new hybrid scheme shows 91% prediction accuracy and 64% coverage for all value producing instructions. We also show that the global stride locality detected by gDiff in load address streams provides strong capabilities in predicting load addresses (coverage 63% and accuracy 86%) and in predicting addresses of missing loads (33% coverage and 53% accuracy).
Guided region prefetching
Authors: Wang Zhenlin , Burger Doug , McKinley Kathryn S. , Reinhardt Steven K. , Weems Charles C.
Published: July 2004

Despite large caches, main-memory access latencies still cause significant performance losses in many applications. Numerous hardware and software prefetching schemes have been proposed to tolerate these latencies. Software prefetching typically provides better prefetch accuracy than hardware, but is limited by prefetch instruction overheads and the compiler's limited ability to schedule prefetches sufficiently far in advance to cover level-two cache miss latencies. Hardware prefetching can be effective at hiding these large latencies, but generates many useless prefetches and consumes considerable memory bandwidth. In this paper, we propose a cooperative hardware-software prefetching scheme called Guided Region Prefetching (GRP), which uses compiler-generated hints encoded in load instructions to regulate an aggressive hardware prefetching engine. We compare GRP against a sophisticated pure hardware stride prefetcher and a scheduled region prefetching (SRP) engine. SRP and GRP show the best performance, with respective 22% and 21% gains over no prefetching, but SRP incurs 180% extra memory traffic---nearly tripling bandwidth requirements. GRP achieves performance close to SRP, but with a mere eighth of the extra prefetching traffic, a 23% increase over no prefetching. The GRP hardware-software collaboration thus combines the accuracy of compilerbased program analysis with the performance potential of aggressive hardware prefetching, bringing the performance gap versus a perfect L2 cache under 20%.
An alternative to branch prediction
Authors: Vintan Lucian N. , Sbera Marius , Mihu Ioan Z. , Florea Adrian
Published: July 2004

Through this paper we developed an alternative approach to the present -- day two level dynamic branch prediction structures. Instead of predicting branches based on history information, we propose to pre - calculate the branch outcome. A pre - calculated branch prediction (PCB) determines the outcome of a branch as soon as all of the branch's operands are known. The instruction that produced the last branch's operand will trigger a supplementary branch condition estimation and, after this operation, it correspondingly computes the branch outcome. This outcome is cached into prediction table. The new proposed PCB algorithm clearly outperforms all the classical branch prediction schemes, simulations on SPEC and Stanford HSA benchmarks, proving to be very efficient. Also, our investigations related to architectural complexity and timing costs are quite optimistic, involving an original alternative to the present-day in branch prediction approach.
A trace-level value predictor for Contrail processors
Authors: Koushiro Takenori , Sato Toshinori , Arita Itsujiro
Published: July 2004

Contrail processors utilize multithreading for improving energy efficiency. In Contrail, an execution of an application is divided into two streams. One is called the speculation stream. It consists of the main part of the execution and is dispatched into the fast functional units. However, several regions of the execution are skipped by utilizing trace-level value prediction. The other stream is called the verification stream. It supports the speculation stream by verifying each data prediction, and is dispatched into the slow units. The key idea is that the trace-level value prediction translates each critical path into non-critical one and moves it from the speculation stream into the verification stream, and then the non-critical instructions are executed on the slow units. In this paper, we investigate a trace-level value predictor for Contrail processors.
Snoopy cache test-and-test-and-set without execessive bus contention
Authors: Glew Andy , Hwu Wen-Mei
Published: July 2004

This paper analyzes the burst of bus traffic that occurs when a lock is released that is being waited for in a test-and-test-and-set spinloop. It is typically
O
(
N
) and can be
O
(
N
2
), depending on assumptions about system behaviour, where N is the number of processors. Supporting a single feature in the bus interface, abandoning pending lock requests, reduces this to
O
(1). Such a feature is already possible on some systems and busses, but has not been applied to synchronization.
IOStone: a synthetic file system benchmark
Authors: Park Arvin , Becker Jeffrey C. , Lipton Richard J.
Published: July 2004

This paper presents a portable benchmark called
IOStone
that measures file system performance on a string of file system requests that is representative of measured system loads. Instead of isolating a particular aspect of file system performance such as disk access speed, or channel bandwidth,
IOStone
measures performance of the entire file system which includes components of disk performance, CPU performance on file system tasks, and disk cache performance,
IOStone
provides a basis for comparing performance of different file system implementations. It can also guide system builders in matching processor performance with file system performance. Measurements made using the
IOStone
benchmark indicate that a good balance between processor performance and file system performance is rarely achieved. Version II of the C language version of
IOStone
is available through electronic mail from becker@iris.ucdavis.edu.
VISA: A variable instruction set architecture
Authors: Gloria Alessandro De
Published: July 2004

This paper presents an instruction coding technique that allows to reduce the instruction width without limiting the exploitation of the machine resources. This result can be obtained by a dynamic instruction coding managed by the compiler.The technique has been applied to a VLIW-structured machine. The machine has an instruction width of 32 bits, while the number of bits needed to code all the functions the machine can perform in a cycle is 98.
Method manipulation in an object-oriented processor
Authors: Lun Mok Pak , Li Richard , Fong Anthony
Published: July 2004

In Object-Oriented Programming (OOP), programmers divide the software applications into small objects, each of which is responsible for performing part of the work. The communications between different objects are through method invocation. Method manipulation is taking a big role in an OOP system. The performance of method invocation would greatly affect the performance of an OOP system. To speed up method communication, an object-oriented computer architecture is proposed at hardware level. High Level Instruction Set Computer (HISC) is one of the OOP architectures proposed. It applies hardware readable data structures to provide mapping of OOP features directly from architectural level. One of the architectural designs that use the concept of HISC is jHISC v3, which is currently under development. It targets to support Java at architecture level.In this paper, we will discuss the method manipulation procedures in jHISC v3 system. By defining the hardware readable data structures for method context, we will see how jHISC v3 processor can use such information to provide a secure method manipulation mechanism for OOP.
The 801 minicomputer
Authors: Radin George
Published: July 2004

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

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

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

storage hierarchy and I/O organization to enable the CPU to execute an instruction at almost every cycle.
Direct execution of lisp on a list_directed architecture
Authors: Sansonnet J. P. , Castan M. , Percebois C. , Botella D. , Perez J.
Published: July 2004

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

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

In turn, the machine has influenced the implementation of LISP. We present here the structure of our LISP interpreter and we give evaluation measures dealing with size, development effort, speed; they prove that programming in LEM is easy, short to debug and very concise. Moreover, the speed of our LISP interpreter confirms that the architecture is very efficient for symbolic processing.
An analysis of a mesa instruction set using dynamic instruction frequencies
Authors: McDaniel Gene
Published: July 2004

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

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

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

Several potential areas for improving the execution speed of a Mesa processor with special purpose hardware are identified.
Heart
Authors: Kamibayashi N. , Ogawana H. , Nagayama K. , Aiso H.
Published: July 2004

This paper discusses the role of microprogramming in operating system design and shows several things: (1) advantages of the efficiency which may be gained from microcoded operating system primitives, (2) selecting the most appropriste primitives for implementation, and (3) an analysis of the tradeoffs among software, firmware, and hardware. The authors propose a practical approach of enhancing computer architecture level, from a view point of functional hierarchy of operating systems. In order to prove the advantages of this approach, we have designed and implemented an experimental abstract machine for an operating system nucleus. This research is an experimental design, and evaluation on its operating system nucleus machine,called HEART. HEART is a set of primitive and universal functions, and works as a nucleus of a multiprogrammed operating system. The research results of our approach are the followings: First, to clarify the properties of operating system nucleus, taking functional hierarchy of operating system into consideration. Second, to show the design of operating system nucleus based on novel concepts. Third, to confirm the possibility of implimenting operating system nucleus machine. Finally, we give a performance evaluation on microcoded HEART and the effectiveness of enhancing computer architecture level based on the properties of operating systems.
Implementation of character string pattern matching on a multiprocessor
Authors: Vineberg Maniel
Published: July 2004

An algorithm to do pattern matching, a basic character string operation, is presented. The Programmable Algorithm Machine (PAM), a proposed special-purpose computer which will feature multiple processing elements and operate efficiently over a wide class of applications, is described. It is shown that the multiple processing elements of the PAM allow concurrent execution of independent operations both in a special case of the pattern matching algorithm, where the string sizes (lengths) are known at compile time, and in the general case, where the sizes are not known.
Aliasing and anti-aliasing in branch history table prediction
Authors: Breen Kristopher C. , Elliott Duncan G.
Published: July 2004

Branch history table (BHT) prediction is a simple and effective method of predicting branch direction at run-time in a microprocessor. Unfortunately, this method suffers from performance limitations due to aliasing, which is when more than one branch uses a single entry in the branch history table. Theoretically, for programs that exhibit pseudo-random branch positioning, aliasing can be predicted and reduced, thereby improving performance. In this paper, we develop a probabilistic model for aliasing and "anti-aliasing", and we use SimpleScalar to explore the extent to which "anti-aliasing" is useful in real programs. Our results show that programs can be "anti-aliased" to some extent when using history tables of 256 entries or greater, and that for large enough history tables, a significant percentage of table entries are unused and available for "anti-aliasing."
How to manage your software product life cycle with MAUI
Authors: Suardi Luigi
Published: July 2004

MAUI monitors multiple software engineering metrics and milestones to analyze a software product's development life cycle in real time.
Proactive information gathering for homeland security teams
Authors: Kogut Paul , Yen John , Leung Yui , Sun Shuang , Wang Rui , Mielczarek Ted , Hellar Ben
Published: July 2004

Supporting counterterrorism analysts with software agents that dynamically anticipate their information requirements.
Cyber defense
Authors: Saydjari O. Sami
Published: July 2004

Seeking the knowledge and means to more methodically detect, defend against, and better understand attacks on networked computer resources.
Rescue robotics for homeland security
Authors: Murphy Robin R.
Published: July 2004

Applying hard-earned lessons to improve human-robot interaction and information gathering.
Segmentation problems
Authors: Kleinberg Jon , Papadimitriou Christos , Raghavan Prabhakar
Published: July 2004

We study a novel genre of optimization problems, which we call
segmentation problems
, motivated in part by certain aspects of clustering and data mining. For any classical optimization problem, the corresponding segmentation problem seeks to partition a set of cost vectors into several
segments
, so that the overall cost is optimized. We focus on two natural and interesting (but MAXSNP-complete) problems in this class, the hypercube segmentation problem and the catalog segmentation problem, and present approximation algorithms for them. We also present a general greedy scheme, which can be specialized to approximate any segmentation problem.
Existential second-order logic over graphs
Authors: Gottlob Georg , Kolaitis Phokion G. , Schwentick Thomas
Published: July 2004

Fagin's theorem, the first important result of descriptive complexity, asserts that a property of graphs is in NP if and only if it is definable by an existential second-order formula. In this article, we study the complexity of evaluating existential second-order formulas that belong to
prefix classses
of existential second-order logic, where a prefix class is the collection of all existential second-order formulas in prenex normal form such that the second-order and the first-order quantifiers obey a certain quantifier pattern. We completely characterize the computational complexity of prefix classes of existential second-order logic in three different contexts: (1) over directed graphs, (2) over undirected graphs with self-loops and (3) over undirected graphs without self-loops. Our main result is that in each of these three contexts a
dichotomy
holds, that is to say, each prefix class of existential second-order logic either contains sentences that can express NP-complete problems, or each of its sentences expresses a polynomial-time solvable problem. Although the boundary of the dichotomy coincides for the first two cases, it changes, as one moves to undirected graphs without self-loops. The key difference is that a certain prefix class, based on the well-known
Ackermann class
of first-order logic, contains sentences that can express NP-complete problems over graphs of the first two types, but becomes tractable over undirected graphs without self-loops. Moreover, establishing the dichotomy over undirected graphs without self-loops turns out to be a technically challenging problem that requires the use of sophisticated machinery from graph theory and combinatorics, including results about graphs of bounded tree-width and Ramsey's theorem.
Patterns of cooperative interaction
Authors: Martin David , Sommerville Ian
Published: July 2004

Patterns of Cooperative Interaction are regularities in the organisation of work, activity, and interaction among participants, and with, through, and around artifacts. These patterns are organised around a framework and are inspired by how such regularities are highlighted in ethnomethodologically-informed ethnographic studies of work and technology. They comprise a high level description and two or more comparable examples drawn from specific studies. Our contention is that these patterns form a useful resource for reusing findings from previous field studies, for enabling analysis and considering design in new settings. Previous work on the relationship between ethnomethodology and design has been concerned primarily in providing presentation frameworks and mechanisms, practical advice, schematisations of the ethnomethodologist's role, different possibilities of input at different stages in development, and various conceptualisations of the relationship between study and design. In contrast, this article seeks to first discuss the position of patterns relative to emergent major topics of interest of these studies. Subsequently it seeks to describe the case for the collection of patterns based on
findings
, their comparison across studies and their general implications for design problems, rather than the concerns of
practical and methodological
interest outlined in the other work. Special attention is paid to our evaluations and to how they inform how the patterns collection may be read, used and contributed to, as well as to reflections on the composition of the collection as it has emerged. The paper finishes, first, with a discussion of how our work relates to other work on patterns, before some closing comments are made on the role of our patterns and ethnomethodology in systems design.
DateLens
Authors: Bederson Benjamin B. , Clamage Aaron , Czerwinski Mary P. , Robertson George G.
Published: July 2004

Calendar applications for small handheld devices are growing in popularity. This led us to develop DateLens, a novel calendar interface for PDAs designed to support complex tasks. It uses a fisheye representation coupled with compact overviews to give the big picture in a small space. The interface also gives users control over the visible time period, as well as supporting integrated search to discover patterns and outliers. Designed with device scalability in mind, DateLens currently runs on desktop computers as well as PDAs. Two user studies were conducted to examine the viability of DateLens as a replacement for traditional calendar visualizations. In the first study, non-PDA users performed complex tasks significantly faster with DateLens than with the Microsoft Pocket PC 2002
TM
calendar (using a PDA emulator). In addition, they rated DateLens as being easier to use than the default calendar application for a majority of the tasks. In the second study, the participants were expert Pocket PC users and the software was run on their own devices. Again, DateLens performed significantly faster for the complex tasks, and there were satisfaction differences favoring each calendar for different kinds of tasks. From these studies, it is clear that DateLens is superior for more complex tasks such as those associated with longer time periods. For daily event tracking, users familiar with the default Pocket PC calendar strongly preferred its daily view and behaviors.
Logic of global synchrony
Authors: Chen Yifeng , Sanders J. W.
Published: July 2004

An intermediate-level specification formalism (i.e., specification language supported by laws and a semantic model), Logs, is presented for PRAM and BSP styles of parallel programming. It extends pre-post sequential semantics to reveal states at points of global synchronization. The result is an integration of the pre-post and reactive-process styles of specification. The language consists of only six commands from which other useful commands can be derived. Parallel composition is simply logical conjunction and hence compositional. A simple predicative semantics and a complete set of algebraic laws are presented. Novel ingredients include the separation, in our reactive context, of the processes for nontermination and for abortion which coincide in standard programming models; the use of partitions, combining the terminating behavior of one program with the nonterminating behavior of another; and a fixpoint operator, the partitioned fixpoint. Our semantics benefits from the recent "healthiness function" approach for predicative semantics. Use of Logs, along with the laws for reasoning about it, is demonstrated on two problems: matrix multiplication (a terminating numerical computation) and the dining philosophers (a reactive computation). The style of reasoning is so close to programming practice that direct transformation from Logs specifications to real PRAM and BSP programs becomes possible.
Hindi CLIR in thirty days
Authors: Larkey Leah S. , Connell Margaret E. , Abduljaleel Nasreen
Published: July 2004

As participants in the TIDES Surprise language exercise, researchers at the University of Massachusetts helped collect Hindi--English resources and developed a cross-language information retrieval system. Components included normalization, stop-word removal, transliteration, structured query translation, and language modeling using a probabilistic dictionary derived from a parallel corpus. Existing technology was successfully applied to Hindi. The biggest stumbling blocks were collection of parallel English and Hindi text and dealing with numerous proprietary encodings.
Archiving scientific data
Authors: Buneman Peter , Khanna Sanjeev , Tajima Keishi , Tan Wang-Chiew
Published: July 2004

Archiving is important for scientific data, where it is necessary to record all past versions of a database in order to verify findings based upon a specific version. Much scientific data is held in a hierachical format and has a key structure that provides a canonical identification for each element of the hierarchy. In this article, we exploit these properties to develop an archiving technique that is both efficient in its use of space and preserves the continuity of elements through versions of the database, something that is not provided by traditional minimum-edit-distance diff approaches. The approach also uses timestamps. All versions of the data are merged into one hierarchy where an element appearing in multiple versions is stored only once along with a timestamp. By identifying the semantic continuity of elements and merging them into one data structure, our technique is capable of providing meaningful change descriptions, the archive allows us to easily answer certain temporal queries such as retrieval of any specific version from the archive and finding the history of an element. This is in contrast with approaches that store a sequence of deltas where such operations may require undoing a large number of changes or significant reasoning with the deltas. A suite of experiments also demonstrates that our archive does not incur any significant space overhead when contrasted with diff approaches. Another useful property of our approach is that we use XML format to represent hierarchical data and the resulting archive is also in XML. Hence, XML tools can be directly applied on our archive. In particular, we apply an XML compressor on our archive, and our experiments show that our compressed archive outperforms compressed diff-based repositories in space efficiency. We also show how we can extend our archiving tool to an external memory archiver for higher scalability and describe various index structures that can further improve the efficiency of some temporal queries on our archive.
Algorithm 830
Authors: Hanson Richard J. , Hopkins Tim
Published: July 2004

First we report on a correction and improvement to the Level 1 BLAS routine
srotmg
for computing the Modified Givens Transformation (MG). We then, in the light of the performance of the code on modern compiler/hardware combinations, reconsider the strategy of supplying separate routines to compute and apply the transformation. Finally, we show that the apparent savings in multiplies obtained by using MG rather than the Standard Givens Transformation (SG) do not always translate into reductions in execution time.
Managing cross-cultural issues in global software outsourcing
Authors: Krishna S. , Sahay Sundeep , Walsham Geoff
Published: July 2004

Exploring research-derived best practices for effective management of global software teams.
Managing academic e-journals
Authors: Hovav Anat , Gray Paul
Published: July 2004

Though e-publishing is relatively inexpensive, e-publisher survival still depends on the age-old virtues of content quality and author credibility.
Unspoken rules of spoken interaction
Authors: Bickmore Timothy W.
Published: July 2004

Body language and familiar silent signals are as much a part of social experience as the conversation. Building systems to recognize and respond to such moves will propel interface technology to the next horizon.
A logic programming approach to knowledge-state planning
Authors: Eiter Thomas , Faber Wolfgang , Leone Nicola , Pfeifer Gerald , Polleres Axel
Published: July 2004

We propose a new declarative planning language, called K, which is based on principles and methods of logic programming. In this language, transitions between states of knowledge can be described, rather than transitions between completely described states of the world, which makes the language well suited for planning under incomplete knowledge. Furthermore, our formalism enables the use of default principles in the planning process by supporting negation as failure. Nonetheless, K also supports the representation of transitions between states of the world (i.e., states of complete knowledge) as a special case, which shows that the language is very flexible. As we demonstrate on particular examples, the use of knowledge states may allow for a natural and compact problem representation. We then provide a thorough analysis of the computational complexity of K, and consider different planning problems, including standard planning and secure planning (also known as
conformant planning
) problems. We show that these problems have different complexities under various restrictions, ranging from NP to NEXPTIME in the propositional case. Our results form the theoretical basis for the DLV
k
system, which implements the language K on top of the DLV logic programming system.
A decomposition-based implementation of search strategies
Authors: Michel Laurent , Van Hentenryck Pascal
Published: July 2004

Search strategies, that is, strategies that describe how to explore search trees, have raised much interest for constraint satisfaction in recent years. In particular, limited discrepancy search and its variations have been shown to achieve significant improvements in efficiency over depth-first search for some classes of applications.This article reconsiders the implementation of discrepancy search, and of search strategies in general, for applications where the search procedure is dynamic, randomized, and/or generates global cuts (or nogoods) that apply to the remaining search. It illustrates that recomputation-based implementations of discrepancy search are not robust with respect to these extensions and require special care which may increase the memory requirements significantly and destroy the genericity of the implementation.To remedy these limitations, the article proposes a novel implementation scheme based on problem decomposition, which combines the efficiency of the recomputation-based implementations with the robustness of traditional iterative implementations. Experimental results on job-shop scheduling problems illustrate the potential of this new implementation scheme, which, surprisingly, may significantly outperform recomputation-based schemes.
Surprise! What's in a Cebuano or Hindi Name?
Authors: May Jonathan , Brunstein Ada , Natarajan Prem , Weischedel Ralph
Published: July 2004

Empirical results are presented for creating training data and training a statistical name learning algorithm on Cebuano and Hindi in roughly three weeks time. The empirical study compares performance in a compressed time frame against performance of the same statistical language model in English (where there was no compressed time frame). Rapid development of several co-reference heuristics in Hindi are also described, and co-reference performance in Hindi is compared to previously developed English techniques.
Making MIRACLEs
Authors: He Daqing , Oard Douglas W. , Wang Jianqiang , Luo Jun , Demner-Fushman Dina , Darwish Kareem , Resnik Philip , Khudanpur Sanjeev , Nossal Michael , Subotin Michael , Leuski Anton
Published: July 2004

Searching is inherently a user-centered process; people pose the questions for which machines seek answers, and ultimately people judge the degree to which retrieved documents meet their needs. Rapid development of interactive systems that use queries expressed in one language to search documents written in another poses five key challenges: (1) interaction design, (2) query formulation, (3) cross-language search, (4) construction of translated summaries, and (5) machine translation. This article describes the design of MIRACLE, an easily extensible system based on English queries that has previously been used to search French, German, and Spanish documents, and explains how the capabilities of MIRACLE were rapidly extended to accommodate Cebuano and Hindi. Evaluation results for the cross-language search component are presented for both languages, along with results from a brief full-system interactive experiment with Hindi. The article concludes with some observations on directions for further research on interactive cross-language information retrieval.
A framework for the integration of partial evaluation and abstract interpretation of logic programs
Authors: Leuschel Michael
Published: July 2004

Recently the relationship between abstract interpretation and program specialization has received a lot of scrutiny, and the need has been identified to extend program specialization techniques so as to make use of more refined abstract domains and operators. This article clarifies this relationship in the context of logic programming, by expressing program specialization in terms of abstract interpretation. Based on this, a novel specialization framework, along with generic correctness results for computed answers and finite failure under SLD-resolution, is developed.This framework can be used to extend existing logic program specialization methods, such as partial deduction and conjunctive partial deduction, to make use of more refined abstract domains. It is also shown how this opens up the way for new optimizations. Finally, as shown in the paper, the framework also enables one to prove correctness of new or existing specialization techniques in a simpler manner.The framework has already been applied in the literature to develop and prove correct specialization algorithms using regular types, which in turn have been applied to the verification of infinite state process algebras.
Snake charmer
Authors: Hendrix Amy
Published: July 2004

Python has become the programming language of choice for a growing legion of passionate devotees
Your blog?
Authors: Weiss Aaron
Published: July 2004

My God, we humans love to hear ourselves talk….or read ourselves write (?!). And no technology has led to such a revolution in navel-gazing as the now-famous blog.
A multiprocessing system for the direct execution of LISP
Authors: Williams Rhon
Published: July 2004

Current implementations were found to be impractical for airborne use due to LISP's incompatability with conventional computer architectures. Direct execution of LISP with tasks distributed between three processors, seemed to be a workable solution. The language was analyzed, and a special token was devised, using a descriptor with a single pointer. Through careful distribution of responsibilities, control and data flow between the processors was minimized. Significant memory savings resulted from ASCII storage and real time garbage collection. A simulation was used to help estimate execution times and showed a factor of 50 to 100 increase in speed. Thus, through the direct execution of LISP by a multiprocessing system, Computer-Aided Decision-Making could be implimented to enhance the safety of flight operations.
Exploiting parallelism in a Relational Associative Processor
Authors: Sadowski Paul J. , Schuster S. A.
Published: July 2004

The Relational Associative Processor (RAP) is a special purpose non-numeric back-end processor used in supporting general Data Base Management Systems. In particular, it is ideally suited for supporting a relational data base. The architecture and instruction set of RAP are discussed in this context. It is the purpose of this paper to show that RAP performance can be enhanced considerably by more fully exploiting its parallel nature. It is shown that a greater degree of concurrent activity will result in better overall performance. An operating system executive to support this high level of concurrency is proposed and modelled using simulation techniques. Both the analytic and simulation results support the value of the proposals.
MAYA
Authors: Zhou Junlan , Ji Zhengrong , Takai Mineo , Bagrodia Rajive
Published: July 2004

The flourish of large-scale network applications across the Internet and or MANET has raised a challenge to network modeling environments that support experimentation and analysis of close interactions between real applications and network dynamics. To facilitate such experimentations, this paper presents
MAYA
, a multiparadigm network modeling framework including discrete event models, analytical models and physical network interfaces, together with its illustrative implementation using QualNet, fluid flow TCP model and physical network interface.
MAYA
framework allows users to interface simulated networks directly with physical networks, while attaining real-time constraints even for large-scale networks by incorporating above multiparadigm network modeling techniques. It also gives user the flexibility to emulate applications on nodes in both real and simulated networks. Experiments are conducted to validate the interoperation of QualNet and fluid flow model, to examine the performance of
MAYA
as well as to evaluate the optimization techniques, namely interleaved execution of fluid flow model and causality-preserve realtime synchronization relaxation. Experimental results indicate that
MAYA
is a scalable and extensible solution to modeling of close interactions between real application and network dynamics.
Staged simulation
Authors: Walsh Kevin , Sirer Emin Gün
Published: July 2004

This article describes
staged simulation
, a technique for improving the run time performance and scale of discrete event simulators. Typical network simulations are limited in speed and scale due to redundant computations encountered both within a single simulation run and between successive runs. Staged simulation proposes to restructure discrete event simulators to operate in stages that precompute, cache, and reuse partial results to drastically reduce redundant computation within and across simulations. We present a general and flexible framework for staging, and identify the advantages and trade-offs of its application to wireless network simulations, a particularly challenging simulation domain. Experience with applying staged simulation to the
ns2
simulator shows that staging can improve execution time by an order of magnitude or more and enable the simulation of wireless networks with tens of thousands of nodes.
Grasping the complexity of IS development projects
Authors: Xia Weidong , Lee Gwanhoo
Published: July 2004

To improve performance of IS development projects, first measure the key dimensions of project complexity and understand how they affect project outcomes.
It's alive
Authors: McGinity Meg
Published: July 2004

Reports of the demise of the telecom industry have been greatly exaggerated.
SIGGRAPH 2004
Authors: Campbell Marisa
Published: July 2004

SIGGRAPH 2004

Conference: August 8-12, 2004
Exhibition: August 10-12, 2004
Los Angeles Convention Center
Los Angeles, CA, USA
Islamic star patterns in absolute geometry
Authors: Kaplan Craig S. , Salesin David H.
Published: July 2004

We present
Najm
, a set of tools built on the axioms of absolute geometry for exploring the design space of Islamic star patterns. Our approach makes use of a novel family of tilings, called "inflation tilings," which are particularly well suited as guides for creating star patterns. We describe a method for creating a parameterized set of motifs that can be used to fill the many regular polygons that comprise these tilings, as well as an algorithm to infer geometry for any irregular polygons that remain. Erasing the underlying tiling and joining together the inferred motifs produces the star patterns. By choice,
Najm
is build upon the subset of geometry that makes no assumption about the behavior of parallel lines. As a consequence, star patterns created by
Najm
can be designed equally well to fit the Euclidean plane, the hyperbolic plane, or the surface of a sphere.