bluuebunny/crossref_metadata_2025 huggingface dataset:
Lifting sequential graph algorithms for distributed-memory parallel computation
Authors: Gregor Douglas , Lumsdaine Andrew
Published: February 2006

This paper describes the process used to extend the Boost Graph Library (BGL) for parallel operation with distributed memory. The BGL consists of a rich set of generic graph algorithms and supporting data structures, but it was not originally designed with parallelism in mind. In this paper, we revisit the abstractions comprising the BGL in the context of distributed-memory parallelism,
lifting
away the implicit requirements of sequential execution and a single shared address space. We illustrate our approach by describing the process as applied to one of the core algorithms in the BGL, breadth-first search. The result is a generic algorithm that is unchanged from the sequential algorithm, requiring only the introduction of external (distributed) data structures for parallel execution. More importantly, the generic implementation retains its interface and semantics, such that other distributed algorithms can be built upon it, just as algorithms are layered in the sequential case. By characterizing these extensions as well as the extension process, we develop general principles and patterns for using (and reusing) generic, object-oriented parallel software libraries. We demonstrate that the resulting algorithm implementations are both efficient and scalable with performance results for several algorithms.
Safe futures for Java
Authors: Welc Adam , Jagannathan Suresh , Hosking Antony
Published: February 2006

A future is a simple and elegant abstraction that allows concurrency to be expressed often through a relatively small rewrite of a sequential program. In the absence of side-effects, futures serve as benign annotations that mark potentially concurrent regions of code. Unfortunately, when computation relies heavily on mutation as is the case in Java, its meaning is less clear, and much of its intended simplicity lost.This paper explores the definition and implementation of
safe
futures for Java. One can think of safe futures as truly transparent annotations on method calls, which designate opportunities for concurrency. Serial programs can be made concurrent simply by replacing standard method calls with future invocations. Most significantly, even though some parts of the program are executed concurrently and may indeed operate on shared data, the semblance of serial execution is nonetheless preserved. Thus, program reasoning is simplified since data dependencies present in a sequential program are not violated in a version augmented with safe futures.Besides presenting a programming model and API for safe futures, we formalize the safety conditions that must be satisfied to ensure equivalence between a sequential Java program and its future-annotated counterpart. A detailed implementation study is also provided. Our implementation exploits techniques such as object versioning and task revocation to guarantee necessary safety conditions. We also present an extensive experimental evaluation of our implementation to quantify overheads and limitations. Our experiments indicate that for programs with modest mutation rates on shared data, applications can use futures to profitably exploit parallelism, without sacrificing safety.
Combining the robustness of checked exceptions with the flexibility of unchecked exceptions using anchored exception declarations
Authors: van Dooren Marko , Steegmans Eric
Published: February 2006

Ever since their invention 30 years ago, checked exceptions have been a point of much discussion. On the one hand, they increase the robustness of software by preventing the manifestation of unanticipated checked exceptions at run-time. On the other hand, they decrease the adaptability of software because they must be propagated explicitly, and must often be handled even if they cannot be signalled.We show that the problems with checked exceptions are caused by a lack of expressiveness of the exceptional return type of a method, which currently dictates a copy & paste style. We add the required expressiveness by introducing anchored exception declarations, which allow the exceptional behavior of a method to be declared relative to that of others. We present the formal semantics of anchored exception declarations, along with the necessary rules for ensuring compile-time safety, and give a proof of soundness. We show that anchored exception declarations do not violate the principle of information hiding when used properly, and provide a guideline for when to use them.We have implemented anchored exception declarations in Cappuccino, which is an extension to the ClassicJava programming language.
Incrementalization across object abstraction
Authors: Liu Yanhong A. , Stoller Scott D. , Gorbovitski Michael , Rothamel Tom , Liu Yanni Ellen
Published: February 2006

Object abstraction supports the separation of what operations are provided by systems and components from how the operations are implemented, and is essential in enabling the construction of complex systems from components. Unfortunately, clear and modular implementations have poor performance when expensive query operations are repeated, while efficient implementations that incrementally maintain these query results are much more difficult to develop and to understand, because the code blows up significantly, and is no longer clear or modular.This paper describes a powerful and systematic method that first allows the "what" of each component to be specified in a clear and modular fashion and implemented straightforwardly in an object-oriented language; then analyzes the queries and updates, across object abstraction, in the straightforward implementation; and finally derives the sophisticated and efficient "how" of each component by incrementally maintaining the results of repeated expensive queries with respect to updates to their parameters. Our implementation and experimental results for example applications in query optimization, role-based access control, etc. demonstrate the effectiveness and benefit of the method.
PolyD
Authors: Cunei Antonio , Vitek Jan
Published: February 2006

The standard dispatching mechanisms built into programming languages are sometimes inadequate to the needs of the programmer. In the case of Java, the need for more flexibility has led to the development of a number of tools, including visitors and multi-method extensions, that each add some particular functionality, but lack the generality necessary to support user-defined dispatching mechanisms. In this paper we advocate a more modular approach to dispatching, and we present a tool, PolyD, that allows the programmer to design custom dispatching strategies and to parametrize many aspects of the dispatching process. PolyD exhibits excellent performance and compares well against existing tools.
X10
Authors: Charles Philippe , Grothoff Christian , Saraswat Vijay , Donawa Christopher , Kielstra Allan , Ebcioglu Kemal , von Praun Christoph , Sarkar Vivek
Published: February 2006

It is now well established that the device scaling predicted by Moore's Law is no longer a viable option for increasing the clock frequency of future uniprocessor systems at the rate that had been sustained during the last two decades. As a result, future systems are rapidly moving from uniprocessor to multiprocessor configurations, so as to use parallelism instead of frequency scaling as the foundation for increased compute capacity. The dominant emerging multiprocessor structure for the future is a
Non-Uniform Cluster Computing
(NUCC) system with nodes that are built out of multi-core SMP chips with non-uniform memory hierarchies, and interconnected in horizontally scalable cluster configurations such as blade servers. Unlike previous generations of hardware evolution, this shift will have a major impact on existing software. Current OO language facilities for concurrent and distributed programming are inadequate for addressing the needs of NUCC systems because they do not support the notions of non-uniform data access within a node, or of tight coupling of distributed nodes.We have designed a modern object-oriented programming language, X10, for high performance, high productivity programming of NUCC systems. A member of the
partitioned global address space
family of languages, X10 highlights the explicit reification of locality in the form of
places
}; lightweight activities embodied in
async
,
future
,
foreach
, and
ateach
constructs; a construct for termination detection (
finish
); the use of lock-free synchronization (
atomic blocks
); and the manipulation of cluster-wide global data structures. We present an overview of the X10 programming model and language, experience with our reference implementation, and results from some initial productivity comparisons between the X10 and Java™ languages.
Planning for disaster with the internet
Authors: Treese Win
Published: February 2006

On October 17, 1989, the Loma Prieta earthquake rocked San Francisco, Oakland, and the area known as Silicon Valley. When I heard the news, I was driving home near Boston, and as I soon as I reached my house, I called some friends to see if they were safe.
Individual displacements for linear probing hashing with different insertion policies
Authors: Janson Svante
Published: February 2006

We study the distribution of the individual displacements in hashing with linear probing for three different versions: First Come, Last Come and Robin Hood. Asymptotic distributions and their moments are found when the the size of the hash table tends to infinity with the proportion of occupied cells converging to some α, 0 < α < 1. (In the case of Last Come, the results are more complicated and less complete than in the other cases.)We also show, using the diagonal Poisson transform studied by Poblete, Viola and Munro, that exact expressions for finitemandncan be obtained from the limits asm,n→ ∞.We end with some results, conjectures and questions about the shape of the limit distributions. These have some relevance for computer applications.
Exact distribution of individual displacements in linear probing hashing
Authors: Viola Alfredo
Published: February 2006

This paper studies the distribution of individual displacements for the standard and the Robin Hood linear probing hashing algorithms. When the a table of size
m
has
n
elements, the distribution of the search cost of a random element is studied for both algorithms. Specifically, exact distributions for fixed
m
and
n
are found as well as when the table is α-full, and α strictly smaller than 1. Moreover, for full tables, limit laws for both algorithms are derived.
Maintaining information in fully dynamic trees with top trees
Authors: Alstrup Stephen , Holm Jacob , Lichtenberg Kristian De , Thorup Mikkel
Published: February 2006

We design top trees as a new simpler interface for data structures maintaining information in a fully dynamic forest. We demonstrate how easy and versatile they are to use on a host of different applications. For example, we show how to maintain the diameter, center, and median of each tree in the forest. The forest can be updated by insertion and deletion of edges and by changes to vertex and edge weights. Each update is supported in
O
(log
n
) time, where
n
is the size of the tree(s) involved in the update. Also, we show how to support nearest common ancestor queries and level ancestor queries with respect to arbitrary roots in
O
(log
n
) time. Finally, with marked and unmarked vertices, we show how to compute distances to a nearest marked vertex. The latter has applications to approximate nearest marked vertex in general graphs, and thereby to static optimization problems over shortest path metrics.Technically speaking, top trees are easily implemented either with Frederickson's [1997a] topology trees or with Sleator and Tarjan's [1983] dynamic trees. However, we claim that the interface is simpler for many applications, and indeed our new bounds are quadratic improvements over previous bounds where they exist.
Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design
Authors: Jothi Raja , Raghavachari Balaji
Published: February 2006

Given an undirected graph
G
= (
V,E
) with
nonnegative costs on its edges, a root node
r
V
, a
set of demands
D
V
with demand
v
D
wishing to route
w(v)
units of flow (weight) to
r
,
and a positive number
k
, the
Capacitated Minimum Steiner
Tree
(CMStT) problem asks for a minimum Steiner tree, rooted at
r
, spanning the vertices in
D
*
{
r
}, in which the sum of the vertex
weights in every subtree connected to
r
is at most
k
.
When
D
=
V
, this problem is known as the
Capacitated Minimum Spanning Tree
(CMST) problem. Both CMsT
and CMST problems are NP-hard. In this article, we present
approximation algorithms for these problems and several of their
variants in network design. Our main results are the following:

---We present a (³ Á

ST

+
2)-approximation algorithm for the CMStT problem, where ³ is
the
inverse Steiner ratio
, and Á

ST

is the best achievable approximation ratio for the Steiner tree
problem. Our ratio improves the current best ratio of
2Á

ST

+ 2 for this problem.

---In particular, we obtain (³ + 2)-approximation ratio for
the CMST problem, which is an improvement over the current best
ratio of 4 for this problem. For points in Euclidean and
rectilinear planes, our result translates into ratios of 3.1548 and
3.5, respectively.

---For instances in the plane, under the
L

p

norm, with the vertices in
D
having uniform weights, we present a nontrivial
(7/5Á

ST

+ 3/2)-approximation algorithm for
the CMStT problem. This translates into a ratio of 2.9 for the CMST
problem with uniform vertex weights in the
L

p

metric plane. Our ratio of 2.9 solves
the long-standing open problem of obtaining any ratio better than 3
for this case.

---For the CMST problem, we show how to obtain a 2-approximation
for graphs in metric spaces with unit vertex weights and
k
=
3,4.

---For the
budgeted
CMST problem, in which the weights of
the subtrees connected to
r
could be up to ±
k
instead of
k
(± e 1), we obtain a ratio of ³
+ 2/±.
Computing almost shortest paths
Authors: Elkin Michael
Published: February 2006

We study the s-sources almost shortest paths
(abbreviated s-ASP) problem. Given an unweighted
graph G = (V,E),
and a subset S ⊆ V
of s nodes, the goal is to compute almost
shortest paths between all the pairs of nodes S
× V. We devise an algorithm with
running time
O(∣E∣nρ
+ s ·
n1 + ζ)
for this problem that computes the paths
Pu,w
for all pairs (u,w) ∈
S × V such that the
length of
Pu,w
is at most (1 + ε)
dG(u,w)
+ β(ζ,ρ,ε), and
β(ζ,ρ,ε) is constant when
ζ, ρ, and ε are arbitrarily small
constants.

We also devise a distributed protocol for the
s-ASP problem that computes the paths
Pu,w
as above, and has time and communication complexities of
O(s ·
Diam(G) +
n1 +
ζ/2) (respectively,
O(s ·
Diam(G) log3
n + n1
+ ζ/2 log n)) and
O(∣E∣
nρ +
s · n1
+ ζ) (respectively,
O(∣E∣
nρ +
s · n1
+ ζ +
n1 + ρ +
ζ(ρ − ζ/2)/2)) in the
synchronous (respectively asynchronous) setting.

Our sequential algorithm, as well as the distributed protocol,
is based on a novel algorithm for constructing (1 +
ε, β(ζ,ρ, ε))-spanners
of size O(n1
+ ζ), developed in this article. This
algorithm has running time of
O(∣E∣
nρ), which is
significantly faster than the previously known algorithm given in
Elkin and Peleg [2001], whose running time is
Õ(n2
+ ρ). We also develop the first
distributed protocol for constructing (1 +
ε,β)-spanners. The communication complexity of
this protocol is near optimal.
An
O
(
VE
) algorithm for ear decompositions of matching-covered graphs
Authors: Carvalho Marcelo H. De , cheriyan joseph
Published: February 2006

Our main result is an
O(nm)
-time (deterministic) algorithm for constructing an ear decomposition of a matching-covered graph, where
n
and
m
denote the number of nodes and edges. The improvement in the running time comes from new structural results that give a sharpened version of Lovász and Plummer's Two-Ear Theorem. Our algorithm is based on
O(nm)
-time algorithms for two other fundamental problems in matching theory, namely, finding all the allowed edges of a graph, and finding the canonical partition of an elementary graph. To the best of our knowledge, no faster deterministic algorithms are known for these two fundamental problems.
Optimizing the SPARK program slicer
Authors: Sward Ricky E. , Baird Leemon C.
Published: February 2006

Recent trends in software re-engineering have included tools to extract program slices from existing Ada procedures. One such tool has already been developed that extracts program slices from SPARK procedures along with a proof that the functionality of the original procedure is equivalent to the functionality of the collection of resulting slices. This paper extends this work by showing how assumptions in the proof can cause inefficiencies in SPARKSlicer and by presenting alternatives that optimize out the inefficiencies. The original proof is modified to show that the SPARK program slicer still produces functionally equivalent program slices from SPARK procedures with these optimizations.
Experimental performance analysis of ada programs in cluster system
Authors: Alexandr Korochkin , Imad Salah , Dmitry Korochkin
Published: February 2006

In this paper, we describe the use of the Ada language for programming in modern cluster systems. The results of experimental performance analysis of Ada and Java programs in a real cluster systems based on dual SMP nodes are presented.
Experiences using SPARK in an undergraduate CS course
Authors: Ruocco Anthony S.
Published: February 2006

This paper describes experiences garnered while teaching a course on high integrity software using SPARK to a mix of junior and senior level undergraduates. The paper describes the impact of pre-requisites, course layout and execution, and lessons learned by students and the instructor. The course used the SPARK toolset provide by Praxis High Integrity Systems, and the Gnat Programming System (GPS) provided by AdaCore Technologies (ACT) under the Ada Academic Initiative Program. Details about using these tools is integrated through out the paper.
SafetyChip
Authors: Naeser Gustaf , Asplund Lars , Furunäs Johan
Published: February 2006

The SafetyChip proposes a strategy where parts of the effort invested in the formal verification during the development of a system can be reused during the system's operation. The strength in a formal verification of a system is that a system can mathematically be proven to fulfil certain requirements, e.g., timing requirements. The SafetyChip uses information from verification to monitor and police a system during run-time. The monitoring is done by surveillance of the applications communication with the run-time kernel. If deviance from the predefined verified behaviour is detected, the SafetyChip can signal (police) this in different ways, e.g., by generating interrupts the system can respond to.In our experiments we use systems written in Ravenscar compliant Ada code and have automated model extraction from source code to the models used to verify the system.This paper presents the functionality and design of the SafetyChip. Properties of an implementation of the SafetyChip are also presented.
AspectAda
Authors: Pedersen Knut H. , Constantinides Constantinos
Published: February 2006

Concerns for concurrent systems are not always easy to modularize within single units using traditional programming languages. The concept of aspect orientation can be applied to allow a modular implementation of these concerns. Existing programming languages has been extended with new language features to support aspect-orientation. The most dominant of these language extensions are AspectJ for the Java programming language. However, Java is not ideal for all types of applications, or there exists legacy systems that need to be maintained.This paper presents AspectAda a new language extension to Ada95 and an AspectAda weaver tool built with the Ada Semantic Interface Specifciation (ASIS). The AspectAda language provides powerful language elements to facilitate aspect oriented programming in domains where Ada's capabilities are of high interest and the AspectAda weaver tool demonstrates the AspectAda language in action.
Data sharing between ada and C/C++
Authors: Mark Matt
Published: February 2006

The En Route Automation Modernization (ERAM) program is a real-time Air Traffic Control (ATC) program being developed by Lockheed Martin Corporation. The ERAM program has high availability requirements, mission critical applications, and stringent response time requirements. The estimated size of the ERAM program is 1,300 KSLOC and includes primarily Ada, C, and C++ code. Legacy code being reused in ERAM is both Ada and C. This resulted in the need for several cross-language interfaces. Standard methods for passing binary data structures between the languages have been developed and will be discussed in this paper.
A comparison of CORBA and ada's distributed systems annex
Authors: Berns Andrew
Published: February 2006

With the recent advent of affordable computers, and the increased computing needs in numerous different fields, distributed computing has become quite popular. Along with this popularity has come several different approaches for creating distributed systems. Ada is fortunate to have multiple approaches available, each distinctively different from each other. One approach is to use a separate middle layer to allow different parts of the Ada distributed program to communicate. The Common Object Request Broker Architecture, or CORBA, uses this approach. Another approach is to use an extension of the language made for the creation of distributed systems, meaning no extra layers need to be added. This language extension approach is used by Ada's Distributed Systems Annex. While both approaches have their merits, CORBA has received much more attention than Ada's Distributed Systems Annex. This paper is the result of an undergraduate research project to examine how easy each approach was, and to see if the extra attention given to CORBA is deserved.
Ada in the avionics industry
Authors: Romanski George
Published: February 2006

All systems installed on aircraft are classified based on the effects they may have on safety. As the systems have become more computerized, Ada has a role to play. Ada has been used successfully in the past, continues to be used at present and is expected to be used in the future. The key components of Ada's success in the avionics industry will be examined. The market is changing and platforms are changing. It is a critical time not to get left behind.
News 2.0
Authors: Stanik John
Published: February 2006

Acoustical Spying Techniques Cooked up in Lab
What’s on Your Hard Drive?
Authors: O'Hanlon Charlene
Published: February 2006

Accordingly, many of our readers are most comfortable working as close to the machine as possible. Sometimes called “bare metal” programmers, they prefer the fewest possible layers of abstraction separating their code from the hardware.
Kode Vicious
Authors: Neville-Neil George
Published: February 2006

KV is back on duty and ready to treat another koding illness: bad APIs. This is one of the most widespread pathologies affecting, and sometimes infecting, us all. But whether we write APIs or simply use APIs (or both), we would all do well to read on and heed the vicious one’s advice.
A Conversation with Ray Ozzie
Authors: O'Hanlon Charlene
Published: February 2006

There are not many names bigger than Ray Ozzie’s in computer programming. An industry visionary and pioneer in computer-supported cooperative work, he began his career as an electrical engineer but fairly quickly got into computer science and programming. He is the creator of IBM’s Lotus Notes and is now chief technical officer of Microsoft, reporting to chief software architect Bill Gates. Recently, Ozzie’s role as chief technical officer expanded as he assumed responsibility for the company’s software-based services strategy across its three major divisions.
Social Bookmarking in the Enterprise
Authors: Millen David , Feinberg Jonathan , Kerr Bernard
Published: February 2006

One of the greatest challenges facing people who use large information spaces is to remember and retrieve items that they have previously found and thought to be interesting. One approach to this problem is to allow individuals to save particular search strings to re-create the search in the future. Another approach has been to allow people to create personal collections of material. Collections of citations can be created manually by readers or through execution of (and alerting to) a saved search.
Review of “Working effectively with legacy code by Michael Feathers”, Prentice Hall PTR, 2004, $44.99 ISBN: 0131177052
Authors: Berzal Fernando
Published: February 2006

Review of “Working effectively with legacy code by Michael Feathers”, Prentice Hall PTR, 2004, $44.99 ISBN: 0131177052
Stop Whining about Outsourcing!
Authors: Patterson David
Published: February 2006

The paranoia inspired by this domino theory of job migration causes American and West European programmers to worry about India, Indian programmers to worry about China, Chinese programmers to worry about the Czech Republic, and so on. Domino theorists must think all IT jobs will go to the Republic of Elbonia, the extremely poor, fourth-world, Eastern European country featured in the Dilbert comic strip.
Energy-conserving data cache placement in sensor networks
Authors: Prabh K. Shashi , Abdelzaher Tarek F.
Published: February 2006

Wireless sensor networks hold a very promising future. The nodes of wireless sensor networks (WSN) have a small energy supply and limited bandwidth available. Since radio communication is expensive in terms of energy consumption, the nodes typically spend most of their energy reserve on wireless communication (rather than on CPU processing) for data dissemination and retrieval. Therefore, the role of energy conserving data communication protocols and services in WSN can not be overemphasized. Caching data at locations that minimize packet transmissions in the network reduces the power consumption in the network, and hence extends its lifetime. Finding locations of the nodes for caching data to minimize communication cost corresponds to finding the nodes of a weighted Minimum Steiner tree whose edge weights depend on the edge's Euclidean length and its data traffic rate. We call this tree a Steiner Data Caching Tree (SDCT). We prove that an optimal SDCT is binary, and that at-least two of the three internal angles formed at the Steiner points are equal. We derive expressions that determine the exact location of a Steiner point for a set of three nodes based on their location and their data refresh rate requirements. Based on these (optimality) results, we present a dynamic distributed energy-conserving application-layer service for data caching and asynchronous multicast. We present the results of simulation of our service that verifies its power saving properties.
Improving key predistribution with deployment knowledge in static sensor networks
Authors: Liu Donggang , Ning Peng
Published: February 2006

Pairwise key establishment is a fundamental security service for sensor networks. However, establishing pairwise keys in sensor networks is a challenging problem, particularly due to the resource constraints on sensor nodes and the threat of node compromises. This article proposes to use both
predeployment and postdeployment knowledge
to improve pairwise key predistribution in static sensor networks. By exploiting the predeployment knowledge, this article first develops two key predistribution schemes, a
closest pairwise keys scheme
and a
closest polynomials scheme
. The analysis shows that these schemes can achieve better performance if the expected location information is available and that the smaller the deployment error is, the better performance they can achieve. The article then investigates how to use
postdeployment knowledge
to improve pairwise key predistribution in static sensor networks. The idea is to load an excessive amount of predistributed keys on sensor nodes, prioritize these keys based on sensors' actual locations discovered after deployment, and discard low-priority keys to thwart node compromise attacks. This approach is then used to improve the random subset assignment scheme proposed recently to demonstrate its practicality and effectiveness. The analysis indicates that the postdeployment knowledge can also greatly improve the performance and security of key predistribution.
FAR
Authors: Huang Qingfeng , Bhattacharya Sangeeta , Lu Chenyang , Roman Gruia-Catalin
Published: February 2006

This article presents FAR, a Face-Aware Routing protocol for mobicast---a spatiotemporal variant of multicast tailored for sensor networks with environmental mobility. FAR features face-routing and timed-forwarding for delivering a message to a mobile delivery zone. Both analytical and statistical results show that FAR achieves reliable spatial and just-in-time message delivery with only moderate communication and memory overhead. This article also presents a novel distributed algorithm for spatial neighborhood discovery for FAR bootstrapping. The spatiotemporal performance and reliability of FAR are demonstrated via network simulations.
On the optimal distribution of sensors in a random field
Authors: Zhang Xin , Wicker Stephen B.
Published: February 2006

This article considers the problem of distributing sensors to observe a random field while meeting a series of energy and coverage constraints. In the network under consideration,
N
identical sensors are to be distributed, with each sensor sending data to a single fusion center at a fixed rate Δ
R
. The problem of sensor allocation to the coverage area is reduced to the problem of allocating sensors to cells by first partitioning the coverage field into cells, and then assuming that sensors in the same cells make the same observations. It is shown that the resulting sensor allocation problem is equivalent to a discrete form of the rate allocation problem, a well-known problem in the field of information theory. General guidelines for solving this problem are provided.
Chinese OOV translation and post-translation query expansion in chinese--english cross-lingual information retrieval
Authors: Zhang Ying , Vines Phil , Zobel Justin
Published: February 2006

Cross-lingual information retrieval allows users to query mixed-language collections or to probe for documents written in an unfamiliar language. A major difficulty for cross-lingual information retrieval is the detection and translation of out-of-vocabulary (OOV) terms; for OOV terms in Chinese, another difficulty is segmentation. At NTCIR-4, we explored methods for translation and disambiguation for OOV terms when using a Chinese query on an English collection. We have developed a new segmentation-free technique for automatic translation of Chinese OOV terms using the web. We have also investigated the effects of distance factor and window size when using a hidden Markov model to provide disambiguation. Our experiments show these methods significantly improve effectiveness; in conjunction with our post-translation query expansion technique, effectiveness approaches that of monolingual retrieval.
Flexible pseudo-relevance feedback via selective sampling
Authors: Sakai Tetsuya , Manabe Toshihiko , Koyama Makoto
Published: February 2006

Although Pseudo-Relevance Feedback (PRF) is a widely used technique for enhancing average retrieval performance, it may actually hurt performance for around one-third of a given set of topics. To enhance the reliability of PRF, Flexible PRF has been proposed, which adjusts the number of pseudo-relevant documents and/or the number of expansion terms for each topic. This paper explores a new, inexpensive Flexible PRF method, called Selective Sampling, which is unique in that it can skip documents in the initial ranked output to look for more “novel” pseudo-relevant documents. While Selective Sampling is only comparable to Traditional PRF in terms of average performance and reliability, per-topic analyses show that Selective Sampling outperforms Traditional PRF almost as often as Traditional PRF outperforms Selective Sampling. Thus, treating the topPdocuments as relevant is often not the best strategy. However, predictingwhenSelective Sampling outperforms Traditional PRF appears to be as difficult as predicting when a PRF method fails. For example, our per-topic analyses show that even the proportion of truly relevant documents in the pseudo-relevant set is not necessarily a good performance predictor.
Comparative study of monolingual and multilingual search models for use with asian languages
Authors: Savoy Jacques
Published: February 2006

Based on the NTCIR-4 test-collection, our first objective is to present an overview of the retrieval effectiveness of nine vector-space and two probabilistic models that perform monolingual searches in the Chinese, Japanese, Korean, and English languages. Our second goal is to analyze the relative merits of the various automated and freely available toolsto translate the English-language topics into Chinese, Japanese, or Korean, and then submit the resultant query in order to retrieve pertinent documents written in one of the three Asian languages. We also demonstrate how bilingual searches could be improved by applying both the combined query translation strategies and data-fusion approaches. Finally, we address basic problems related to multilingual searches, in which queries written in English are used to search documents written in the English, Chinese, Japanese, and Korean languages.
Proposal of two-stage patent retrieval method considering the claim structure
Authors: Mase Hisao , Matsubayashi Tadataka , Ogawa Yuichi , Iwayama Makoto , Oshio Tadaaki
Published: February 2006

The importance of patents is increasing in global society. In preparing a patent application, it is essential to search for related patents that may invalidate the invention. However, it is time-consuming to identify them among the millions of patents. This article proposes a patent-retrieval method that considers a claim structure for a more accurate search for invalidity. This method uses a claim text as input; it consists of two retrieval stages. In stage 1, general text analysis and retrieval methods are applied to improve recall. In stage 2, the top N documents retrieved in stage 1 are rearranged to improve precision by applying text analysis and retrieval methods using the claim structure. Our two-stage retrieval introduces five precision-oriented analysis and retrieval methods: query-term extraction from a portion of a claim text that describes the characteristics of a claim; query term-weighting without term frequency; query term-weighting with “measurement terms”; text retrieval using only claims as a target; and calculating the relevant score by “partially” adding scores in stage 2 to those in stage 1. Evaluation results using test sets of the NTCIR4 Patent Retrieval Task show that our methods are effective, though the degree of the effectiveness varies depending on the test sets.
Introduction to the special issue on the 2005 workshop on design, analysis, and simulation of chip multiprocessors (dasCMP'05)
Authors: Jouppi Norman P. , Kumar Rakesh , Tullsen Dean
Published: February 2006

Chip multiprocessor architectures are becoming increasingly attractive as an option to provide high instruction throughput while keeping power and complexity under control. Such architectures have also been shown to have scalability and productivity advantages. Multi-core processors are fast becoming mainstream.
Performance/Watt
Authors: Laudon James
Published: February 2006

Transaction processing has emerged as the killer application for commercial servers. Most servers are engaged in transactional workloads such as processing search requests, serving middleware, evaluating decisions, managing databases, and powering online commerce. Currently, commercial servers are built from one or more high-performance superscalar processors. However, commercial server applications exhibit high cache miss rates, large memory footprints, and low instruction level parallelism (ILP), which leads to poor utilization on traditional ILP-focused superscalar processors [11]. In addition, these ILP-focused processors have been primarily optimized to deliver maximum performance by employing high clock rates and large amounts of speculation. As a result, we are now at the point where the performance/Watt of subsequent generations of traditional ILP-focused processors on server workloads has been flat [4] or even decreasing. The lack of increase in processor performance/Watt, coupled with the continued decrease in server hardware acquisition costs and likely increases in future power and cooling costs is leading to a situation where total cost of server ownership will soon be predominately determined by power [4]. In this paper, we argue that attacking thread-level parallelism (TLP) via a large number of simple cores on a chip multiprocessor (CMP) leads to much better performance/Watt for server workloads. As a case study, we compare Sun's TLP-oriented Niagara processor against the ILP-oriented dual-core Pentium Extreme Edition from Intel, showing that the Niagara processor has a significant performance/Watt advantage for throughput-oriented server applications.
A chip prototyping substrate
Authors: Davis John D. , Richardson Stephen E. , Charitsis Charis , Olukotun Kunle
Published: February 2006

We describe a hybrid hardware emulation environment: the Flexible Architecture for Simulation and Testing (FAST). FAST integrates field-programmable gate arrays (FPGAs), microprocessors, and memory to enable rapid prototyping of chip multiprocessors, multithreaded architectures, or other novel computer architectures and chip-level memory systems. FAST combines configurable and fixed-function hardware and software to facilitate rapid prototyping by utilizing components optimized for their particular tasks: FPGAs for interconnect and glue logic; processors for rapid program execution; and SRAMs for fast memory. Unlike software simulators, FAST can simulate complex designs at multi-megahertz speeds regardless of the simulation detail. We illustrate FAST's utility by describing mappings of both a small-scale CMP with speculation support and a large-scale CMP connected using a network. We then show performance results from a very simple, decoupled 4-way CMP executing small test programs.
Chip multi-processor scalability for single-threaded applications
Authors: Vachharajani Neil , Iyer Matthew , Ashok Chinmay , Vachharajani Manish , August David I. , Connors Daniel
Published: February 2006

The exponential increase in uniprocessor performance has begun to slow. Designers have been unable to scale performance while managing thermal, power, and electrical effects. Furthermore, design complexity limits the size of monolithic processors that can be designed while keeping costs reasonable. Industry has responded by moving toward chip multi-processor architectures (CMP). These architectures are composed from replicated processors utilizing the die area afforded by newer design processes. While this approach mitigates the issues with design complexity, power, and electrical effects, it does nothing to directly improve the performance of contemporary or future single-threaded applications.This paper examines the scalability potential for exploiting the parallelism in single-threaded applications on these CMP platforms. The paper explores the total available parallelism in unmodified sequential applications and then examines the viability of exploiting this parallelism on CMP machines. Using the results from this analysis, the paper forecasts that CMPs, using the "intrinsic" parallelism in a program, can sustain the performance improvement users have come to expect from new processors for only 6-8 years provided many successful parallelization efforts emerge. Given this outlook, the paper advocates exploring methodologies which achieve parallelism beyond this "intrinsic" limit of programs.
Hardware-modulated parallelism in chip multiprocessors
Authors: Chen Julia , Juang Philo , Ko Kevin , Contreras Gilberto , Penry David , Rangan Ram , Stoler Adam , Peh Li-Shiuan , Martonosi Margaret
Published: February 2006

Chip multi-processors (CMPs) already have widespread commercial availability, and technology roadmaps project enough on-chip transistors to replicate tens or hundreds of current processor cores. How will we express parallelism, partition applications, and schedule/place/migrate threads on these highly-parallel CMPs?This paper presents and evaluates a new approach to highly-parallel CMPs, advocating a new hardware-software contract. The software layer is encouraged to expose large amounts of multi-granular, heterogeneous parallelism. The hardware, meanwhile, is designed to offer low-overhead, low-area support for orchestrating and modulating this parallelism on CMPs at runtime. Specifically, our proposed CMP architecture consists of architectural and ISA support targeting thread creation, scheduling and context-switching, designed to facilitate effective hardware run-time mapping of threads to cores at low overheads.Dynamic modulation of parallelism provides the ability to respond to run-time variability that arises from dataset changes, memory system effects and power spikes and lulls, to name a few. It also naturally provides a long-term CMP platform with performance portability and tolerance to frequency and reliability variations across multiple CMP generations. Our simulations of a range of applications possessing do-all, streaming and recursive parallellism show speedups of 4-11.5X and energy-delay-product savings of 3.8X, on average, on a 16-core vs. a 1-core system. This is achieved with modest amounts of hardware support that allows for low overheads in thread creation, scheduling and context-switching. In particular, our simulations motivated the need for hardware support, showing that the large thread management overheads of current run-time software systems can lead to up to 6.5X slowdown. The difficulties faced in static scheduling were shown in our simulations with a static scheduling algorithm, fed with oracle profiled inputs suffering up to 107% slowdown compared to NDP's hardware scheduler, due to its inability to handle memory system variabilities. More broadly, we feel that the ideas presented here show promise for scaling to the systems expected in ten years, where the advantages of high transistor counts may be dampened by difficulties in circuit variations and reliability. These issues will make dynamic scheduling and adaptation mandatory; our proposals represent a first step towards that direction.
Dynamically configurable shared CMP helper engines for improved performance
Authors: Shayesteh Anahita , Reinman Glenn , Jouppi Norman , Sair Suleyman , Sherwood Tim
Published: February 2006

Technology scaling trends have forced designers to consider alternatives to deeply pipelining aggressive cores with large amounts of performance accelerating hardware. One alternative is a small, simple core that can be augmented with latency tolerant helper engines. As the demands placed on the processor core varies between applications, and even between phases of an application, the benefit seen from any set of helper engines will vary tremendously. If there is a single core, these auxiliary structures can be turned on and off dynamically to tune the energy/performance of the machine to the needs of the running application.As more of the processor is broken down into helper engines, and as we add more and more cores onto a single chip which can potentially share helpers, the decisions that are made about these structures become increasingly important. In this paper we describe the need for methods that effectively manage these helper engines. Our counter-based approach can dynamically turn off 3 helpers on average, while staying within 2% of the performance when running with all helpers. In a multicore environment, our intelligent and flexible sharing of helper engines, provides an average 24% speedup over static sharing in conjoined cores. Furthermore we show benefit from constructively sharing helper engines among multiple cores running the same application.
Performance implications of single thread migration on a chip multi-core
Authors: Constantinou Theofanis , Sazeides Yiannakis , Michaud Pierre , Fetis Damien , Seznec Andre
Published: February 2006

High performance multi-core processors are becoming an industry reality. Although multi-cores are suited for multithreaded and multi-programmed workloads, many applications are still mono-thread and multi-core performance with a single thread workload is an important issue. Furthermore, recent studies suggest that performance, power and temperature considerations of future multi-cores may necessitate activity-migration between cores.Motivated by the above, this paper investigates the performance implications of single thread migration on a multi-core. Specifically, the study considers the influence on the performance of a single thread of the following migration and multi-core parameters: frequency of migration, core warm-up modes, subset of resources that are warmed-up, number of cores, and cache hierarchy organization. The results of this study can provide insight to architects on how to design performance-efficient power and thermal strategies for a multi-core chip.The experimental results, for the benchmarks and microarchitectures used in this study, show that the performance loss due to activity migration on a multi-core with private L1s and a shared L2 can be minimized if: (a) a migrating thread continues its execution on a core that was previously visited by the thread, and (b) cores remember their predictor state since their previous activation (all other core resources can be cold). The analogous conclusions for a multi-core with private L1s and L2s and a shared L3 are: remembering the predictor state, maintaining the tags of the various L2 caches coherent and allowing L2-L2 data transfers from inactive cores to the active core.The data also show that when migration period is at least every 160K cycles, the transfer of register state between two cores and the flushing of dirty private L1 data have a negligible performance overhead.
Multifacet's general execution-driven multiprocessor simulator (GEMS) toolset
Authors: Martin Milo M. K. , Sorin Daniel J. , Beckmann Bradford M. , Marty Michael R. , Xu Min , Alameldeen Alaa R. , Moore Kevin E. , Hill Mark D. , Wood David A.
Published: February 2006

The Wisconsin Multifacet Project has created a simulation toolset to characterize and evaluate the performance of multiprocessor hardware systems commonly used as database and web servers. We leverage an existing full-system functional simulation infrastructure (Simics [14]) as the basis around which to build a set of timing simulator modules for modeling the timing of the memory system and microprocessors. This simulator infrastructure enables us to run architectural experiments using a suite of scaled-down commercial workloads [3]. To enable other researchers to more easily perform such research, we have released these timing simulator modules as the Multifacet General Execution-driven Multiprocessor Simulator (GEMS) Toolset, release 1.0, under GNU GPL [9].