bluuebunny/crossref_metadata_2025 huggingface dataset:
Privacy protection in personalized search
Authors: Shen Xuehua , Tan Bin , Zhai ChengXiang
Published: September 2007

Personalized search is a promising way to improve the accuracy of web search, and has been attracting much attention recently. However, effective personalized search requires collecting and aggregating user information, which often raise serious concerns of privacy infringement for many users. Indeed, these concerns have become one of the main barriers for deploying personalized search applications, and how to do privacy-preserving personalization is a great challenge. In this paper, we systematically examine the issue of privacy preservation in personalized search. We distinguish and define four levels of privacy protection, and analyze various software architectures for personalized search. We show that client-side personalization has advantages over the existing server-side personalized search services in preserving privacy, and envision possible future strategies to fully protect user privacy.
On rank correlation in information retrieval evaluation
Authors: Melucci Massimo
Published: September 2007

Some methods for rank correlation in evaluation are examined and their relative advantages and disadvantages are discussed. In particular, it is suggested that different test statistics should be used for providing additional information about the experiments other that the one provided by statistical significance testing. Kendall's τ is often used for testing-rank correlation, yet it is little appropriate if the objective of the test is different from what τ was designed for. In particular, attention should be paid to the null hypothesis. Other measures for rank correlation are described. If one test statistic suggests to reject a hypothesis, other test statistics should be used to support or to revise the decision. The paper then focuses on rank correlation between webpage lists ordered by PageRank for applying the general reflections on these test statistics. An interpretation of PageRank behaviour is provided on the basis of the discussion of the test statistics for rank correlation.
Presentation schemes for component analysis in IR experiments
Authors: Kantor Paul , Lin Jimmy
Published: September 2007

Information retrieval research, at least as conceived by the SIGIR community, is fundamentally experimental in nature. As such, the presentation of results from controlled, reproducible experiments lies at the core of our work. Many reports follow the same general format: authors propose a new retrieval method, whose performance on some well-defined task is compared against a baseline. Authors also report results from alternative configurations, e.g., variations in parameters, turning off (ablation) of different components, etc. The presentation of experimental results forms an integral part of the conferences and journals that comprise the medium in which knowledge is disseminated.
Evaluating XML retrieval effectiveness at INEX
Authors: Lalmas Mounia , Tombros Anastasios
Published: September 2007

The INitiative for the Evaluation of XML retrieval (INEX) was set up in 2002 to establish an infrastructure and provide means, in the form of large test collections and appropriate scoring methods, for evaluating the effectiveness of content-oriented XML retrieval systems. This report provides an overview of the evaluation methodology developed in INEX from 2002 to 2006.
The use case track at INEX 2006
Authors: Pharo Nils , Trotman Andrew
Published: September 2007

XML information retrieval in the INEX workshop series has, for a large part, focused on creating algorithms for testing against the test collections provided by the IEEE and Wikipedia. The use case track is a new track at INEX and represents an attempt at identifying examples of how XML IR systems can be exploited by end-users for various purposes. In the present article we present a summary of the discussions and findings of the track.
Report on the INEX 2005 interactive track
Authors: Malik Saadia , Larsen Birger , Tombros Anastasios
Published: September 2007

The overall motivation for the Interactive Track (iTrack) at INEX is twofold. First, to investigate the behaviour of users when interacting with components of XML documents, and secondly to investigate and develop approaches for XML retrieval which are effective in user-based environments. One of the major outcomes of the track in 2004 was the need to investigate methods that can be supportive during the search process based on features extracted from the XML formatting[1][2]. Problems that might be solved using such methods include overlapping components and the presentation of retrieved elements in the result list. In the experimental system that was offered in 2005, these two issues were addressed. This offered the opportunity to study how overall user search behaviour was affected by these changes when compared to the behaviour observed in 2004. In addition, the following issues were addressed in 2005, following the recommendations of the INEX Methodology Workshop at the Glasgow IR Festival
1
.
Report on the INEX 2006 heterogeneous collection track
Authors: Frommholz Ingo , Larson Ray
Published: September 2007

XML collections that consist of subcollections from different sources pose a challenge with respect to syntactic, semantic and genre heterogeneity, because they are based on different DTDs or schemas, cover various topics and consist of diverse document types. This led to the establishment of the Heterogeneous Track at INEX 2006. The goal of the track was to set up a testbed consisting of several different and diverse collections and defining retrieval tasks and appropriate topics. These are the foundations for the Heterogeneous Track at INEX 2007, where the focus is on run submissions, relevance assessments and proper evaluation of the proposed methods dealing with a heterogeneous collection.
Overview of the TREC 2006 ciQA task
Authors: Kelly Diane , Lin Jimmy
Published: September 2007

Growing interest in interactive systems for answering complex questions lead to the development of the complex, interactive QA (ciQA) task, introduced for the first time at TREC 2006. This paper describes the rationale and design of the ciQA task and the evaluation results. Thirty complex relationship questions based on five question templates were investigated using the AQUAINT collection of newswire text. Interaction forms were the primary vehicle for defining and capturing user-system interactions. In total, six groups participated in the ciQA task and contributed ten different sets of interaction forms. There were two main findings: baseline IR techniques are competitive for complex QA and interaction, at least as defined and implemented in this evaluation, did not appear to improve performance by much.
Federated search of text search engines in uncooperative environments
Authors: Si Luo
Published: September 2007

Conventional search engines like Google provide access to Web information that can be acquired easily by crawling hyperlinks. However, a large amount of information cannot be copied arbitrarily by conventional search engines. This type of hidden information, which is very valuable, can only be accessed via an alternative search model other than the centralized retrieval model used by conventional search engines.
Full-text federated search in peer-to-peer networks
Authors: Lu Jie
Published: September 2007

Peer-to-peer (P2P) networks integrate autonomous computing resources without requiring a central coordinating authority, which makes them a potentially robust and scalable model for providing federated search capability to large-scale networks of text digital libraries. However, P2P networks have so far mostly used simple search techniques based on document names or controlled-vocabulary terms, and provided very limited support for full-text search of document contents.
Computerized voting
Authors: Amurao David
Published: September 2007

At first glance, electronic voting can seem to be an end-all solution to the problems produced by the "chad-prone" punch-card ballots in the 2000 Florida recount, as well as to the limitations and problems of other types of ballots. Electronic voting offers advantages to both the voter and the polling place in its efficiency, speed, and convenience. However, electronic voting is prone to other types of problems that are inherent in computers themselves. Votes can be greatly skewed in these computerized voting machines by a plethora of factors such as glitches, hackers, viruses and even by the voting machine makers who may be sympathetic to particular political parties. In using these computerized voting systems nationally, the votes of millions of Americans may be compromised. Still, these computer-related problems can be fixed and the systems can be made more secure with rigorous testing and evaluation by independent computer science experts. Many changes regarding security and reliability must be implemented to even consider computerized voting systems for national use.
Democracy's downfall
Authors: Gaines Joshua
Published: September 2007

Our Founding Fathers wanted to live in a country of freedom. To serve the people, democracy was born as our government. Electing whom they want to represent them in office, the people have the power to vote for a candidate of their choosing. However, this power is disintegrating due to the extreme errors caused by electronic voting machines. In the year 2000, one out of every nine voting precincts used electronic voting machines (Fisher "Election" 4). Tadayoshi Kohno says, "Our analysis shows that this voting system is far below even the most minimal security standards applicable in other contexts" (Kohno 1). The sum of all the errors caused by these machines greatly threatens our democracy.
Direct recording electronic voting machines (DRE's) are not ready for national use.
Voter verified ballots
Authors: Linton Alexa
Published: September 2007

Americans' right to vote validates the American government as a true democracy. Congress passed the Help America Vote Act (HAVA) in the fall of 2002 to make elections more secure after the debacle in Florida in the 2000 presidential election. While HAVA was intended to make elections more secure and reliable, it has in fact had the opposite effect, even threatening to undermine the very foundations of democracy. HAVA, as commonly interpreted, has forced states to purchase electronic voting machines, most of which, including the ones just purchased by Bucks County, Pennsylvania, provide absolutely no voter verifiable paper ballot. This eliminates any possibility to recount or audit the vote. Paperless electronic voting machines are not only expensive but can also be easily rigged to fix an election. They have weak security systems that can easily be tampered with, proprietary software that is kept secret by the manufacturer, and are already notorious for losing or miscounting votes. These machines should not be used because of their high cost, vulnerability to hacking and fraud, unreliability, and most of all because of their lack of a voter verifiable receipt.
Faster algorithms for sorting by transpositions and sorting by block interchanges
Authors: Feng Jianxing , Zhu Daming
Published: September 2007

In this article, we present a new data structure, called the permutation tree, to improve the running time of sorting permutation by transpositions and sorting permutation by block interchanges. The existing 1.5-approximation algorithm for sorting permutation by transpositions has time complexity
O
(
n
3/2
√
logn
). By means of the permutation tree, we can improve this algorithm to achieve time complexity
O
(
nlogn
). We can also improve the algorithm for sorting permutation by block interchanges to take its time complexity from
O
(
n
2
) down to
O
(
nlogn
).
Constructing pairwise disjoint paths with few links
Authors: Gupta Himanshu , Wenger Rephael
Published: September 2007

Let
P
be a simple polygon and let {(
u
1
,
u
′
1
), (
u
2
,
u
′
2
),…,(
u
m
,
u
′
m
)} be a set of
m
pairs of distinct vertices of
P
, where for every distinct
i
,
j
≤
m
, there exist pairwise disjoint (nonintersecting) paths connecting
u

i

to
u
′

i

and
u

j

to
u
′

j

. We wish to construct
m
pairwise disjoint paths in the interior of
P
connecting
u
i
to
u
′

i

for
i
= 1, …,
m
, with a minimal total number of line segments. We give an approximation algorithm that constructs such a set of paths using
O
(
M
) line segments in
O
(
n
log
m
+
M
log
m
) time, where
M
is the number of line segments in the optimal solution and
n
is the size of the polygon.
Multicommodity demand flow in a tree and packing integer programs
Authors: Chekuri Chandra , Mydlarz Marcelo , Shepherd F. Bruce
Published: September 2007

We consider requests for capacity in a given tree network
T
= (
V
,
E
) where each edge
e
of the tree has some integer capacity
u
e
. Each request
f
is a node pair with an integer demand
d
f
and a profit
w
f
which is obtained if the request is satisfied. The objective is to find a set of demands that can be feasibly routed in the tree and which provides a maximum profit. This generalizes well-known problems, including the knapsack and
b
-matching problems.

When all demands are 1, we have the integer multicommodity flow problem. Garg et al. [1997] had shown that this problem is NP-hard and gave a 2-approximation algorithm for the cardinality case (all profits are 1) via a primal-dual algorithm. Our main result establishes that the integrality gap of the natural linear programming relaxation is at most 4 for the case of arbitrary profits. Our proof is based on coloring paths on trees and this has other applications for wavelength assignment in optical network routing.

We then consider the problem with arbitrary demands. When the maximum demand
d
max
is at most the minimum edge capacity
u
min
, we show that the integrality gap of the LP is at most 48. This result is obtained by showing that the integrality gap for the demand version of such a problem is at most 11.542 times that for the unit-demand case. We use techniques of Kolliopoulos and Stein [2004, 2001] to obtain this. We also obtain, via this method, improved algorithms for line and ring networks. Applications and connections to other combinatorial problems are discussed.
Windows scheduling as a restricted version of bin packing
Authors: Bar-Noy Amotz , Ladner Richard E. , Tamir Tami
Published: September 2007

Given is a sequence of
n
positive integers
w
1
,
w
2
,…,
w

n

that are associated with the items 1,2,…
n
, respectively. In the
windows scheduling
problem, the goal is to schedule all the items (equal-length information pages) on broadcasting channels such that the gap between two consecutive appearances of page
i
on any of the channels is at most
w
i
slots (a slot is the transmission time of one page). In the
unit-fractions bin packing
problem, the goal is to pack all the items in bins of unit size where the size (width) of item
i
is 1/
w

i

. The optimization objective is to minimize the number of channels or bins. In the offline setting, the sequence is known in advance, whereas in the online setting, the items arrive in order and assignment decisions are irrevocable. Since a page requires at least 1/
w

i

of a channel's bandwidth, it follows that windows scheduling without migration (i.e., all broadcasts of a page must be from the same channel) is a restricted version of unit-fractions bin packing.

Let
H
= ⌈Σ

i
==1

n

(1/
w

i

) be the bandwidth lower bound on the required number of bins (channels). The best-known offline algorithm for the windows scheduling problem used
H
+
O
(ln
H
) channels. This article presents an offline algorithm for the unit-fractions bin packing problem with at most
H
+ 1 bins. In the online setting, this article presents algorithms for both problems with
H
+
O
(√
H
) channels or bins, where the one for the unit-fractions bin packing problem is simpler. On the other hand, this article shows that already for the unit-fractions bin packing problem, any online algorithm must use at least
H
+Ω(ln
H
) bins. For instances in which the window sizes form a divisible sequence, an optimal online algorithm is presented. Finally, this article includes a new NP-hardness proof for the windows scheduling problem.
Approximate parameterized matching
Authors: Hazay Carmit , Lewenstein Moshe , Sokol Dina
Published: September 2007

Two equal length strings
s
and
s
′, over alphabets Σ

s

and Σ

s

′,
parameterize match
if there exists a bijection π : Σ

s

→ Σ

s

′ such that π (
s
) =
s
′, where π (
s
) is the renaming of each character of
s
via π.
Parameterized matching
is the problem of finding all parameterized matches of a pattern string
p
in a text
t
, and
approximate parameterized matching
is the problem of finding at each location a bijection π that maximizes the number of characters that are mapped from
p
to the appropriate |
p
|-length substring of
t
.

Parameterized matching was introduced as a model for software duplication detection in software maintenance systems and also has applications in image processing and computational biology. For example, approximate parameterized matching models image searching with variable color maps in the presence of errors.

We consider the problem for which an error threshold,
k
, is given, and the goal is to find all locations in
t
for which there exists a bijection π which maps
p
into the appropriate |
p
|-length substring of
t
with at most
k
mismatched mapped elements. Our main result is an algorithm for this problem with
O
(
nk
1.5
+
mk
log
m
) time complexity, where
m
= |
p
| and
n
=|
t
|. We also show that when |
p
| = |
t
| =
m
, the problem is equivalent to the maximum matching problem on graphs, yielding a
O
(
m
+
k
1.5
) solution.
Improved approximation results for the stable marriage problem
Authors: Halldórsson Magnús M. , Iwama Kazuo , Miyazaki Shuichi , Yanagisawa Hiroki
Published: September 2007

The stable marriage problem has recently been studied in its general setting, where both ties and incomplete lists are allowed. It is NP-hard to find a stable matching of maximum size, while any stable matching is a maximal matching and thus trivially we can obtain a 2-approximation algorithm.

In this article, we give the first nontrivial result for approximation of factor less than two. Our algorithm achieves an approximation ratio of 2/(1 +
L
−2
) for instances in which only men have ties of length at most
L
. When both men and women are allowed to have ties but the lengths are limited to two, then we show a ratio of 13/7(<1.858). We also improve the lower bound on the approximation ratio to 21/19(>1.1052).
Convergence time to Nash equilibrium in load balancing
Authors: Even-Dar Eyal , Kesselman Alex , Mansour Yishay
Published: September 2007

We study the number of steps required to reach a pure Nash equilibrium in a load balancing scenario where each job behaves selfishly and attempts to migrate to a machine which will minimize its cost. We consider a variety of load balancing models, including identical, restricted, related, and unrelated machines. Our results have a crucial dependence on the weights assigned to jobs. We consider arbitrary weights, integer weights,
k
distinct weights, and identical (unit) weights. We look both at an arbitrary schedule (where the only restriction is that a job migrates to a machine which lowers its cost) and specific efficient schedulers (e.g., allowing the largest weight job to move first). A by-product of our results is establishing a connection between various scheduling models and the game-theoretic notion of potential games. We show that load balancing in unrelated machines is a generalized ordinal potential game, load balancing in related machines is a weighted potential game, and load balancing in related machines and unit weight jobs is an exact potential game.
Routing and scheduling in multihop wireless networks with time-varying channels
Authors: Andrews Matthew , Zhang Lisa
Published: September 2007

We study routing and scheduling in
multihop wireless networks
. When data is transmitted from its source node to its destination node it may go through other wireless nodes as intermediate hops. The data transmission is
node constrained
, that is, every node can transmit data to at most one neighboring node per time step. The transmission rates are
time varying
as a result of changing wireless channel conditions.

In this article, we assume that data arrivals and transmission rates are governed by an
adversary
. The power of the adversary is limited by an admissibility condition which forbids the adversary from overloading any wireless node a priori. The node-constrained transmission and time-varying nature of the transmission rates make our model different from and harder than the standard adversarial queueing model which relates to wireline networks.

For the case in which the adversary specifies the paths that the data must follow, we design scheduling algorithms that ensure network stability. These algorithms try to give priority to the data that is closest to its source node. However, at each time step only a subset of the data queued at a node is eligible for scheduling. One of our algorithms is fully
distributed
.

For the case in which the adversary does not dictate the data paths, we show how to route data so that the admissibility condition is satisfied. We can then schedule data along the chosen paths using our stable scheduling algorithms.
Novel architectures for P2P applications
Authors: Naor Moni , Wieder Udi
Published: September 2007

We propose a new approach for constructing P2P networks based on a dynamic decomposition of a continuous space into cells corresponding to servers. We demonstrate the power of this approach by suggesting two new P2P architectures and various algorithms for them. The first serves as a DHT (distributed hash table) and the other is a dynamic expander network. The DHT network, which we call Distance Halving, allows logarithmic routing and load while preserving constant degrees. It offers an optimal tradeoff between degree and path length in the sense that degree
d
guarantees a path length of
O
(log

d

n
). Another advantage over previous constructions is its relative simplicity. A major new contribution of this construction is a dynamic caching technique that maintains low load and storage, even under the occurrence of hot spots. Our second construction builds a network that is guaranteed to be an expander. The resulting topologies are simple to maintain and implement. Their simplicity makes it easy to modify and add protocols. A small variation yields a DHT which is robust against random Byzantine faults. Finally we show that, using our approach, it is possible to construct
any
family of constant degree graphs in a dynamic environment, though with worse parameters. Therefore, we expect that more distributed data structures could be designed and implemented in a dynamic environment.
HIPPA, privacy and organizational change
Authors: Jensen Bradley K. , Cline Melinda , Guynes Carl S.
Published: September 2007

Organizational change surrounding the security of identifiable health information has become imperative. This is a significant challenge for managers who are held responsible for loss of privacy through faulty security procedures. Management cannot completely secure the organization and still provide employees and customers with the information and services they need. Organizations must decide how much and what type of security they need, how to assign priorities, and how to manage security as the organization evolves in a competitive environment.
Disclosive computer ethics?
Authors: Messerly John G.
Published: September 2007

In his article "Disclosive Computer Ethics," Phillip Brey critiques mainstream computer ethics (MCE) and argues for a disclosive computer ethic (DCE) "which is concerned with the moral deciphering of embedded values and norms in computer systems, applications, and practices."
1
In this article I argue that DCE simply shifts the focus of MCE toward issues Brey deems important.
Some steps towards implementing E-government
Authors: Sagheb-Tehrani Mehdi
Published: September 2007

Governments around the world are implementing electronic government. Today governments at all levels reply to millions of citizen queries electronically. Electronic-government (e-government) promises accurate, agile, transactions and delivery of services and information to businesses, citizens and governments agencies. More, e-government plays a part towards the enhancement of democracy. Beyond doubt businesses continue to interact electronically with other businesses and their clients because they have to do so, in order to be efficient. E-government utilizes information technology (IT) to provide all the access to a wide range of public services. This paper puts forward some steps for a better implementation of electronic government. The paper disputes that several key success factors are appropriate for e-government implementation.
Unauthorized copying of software
Authors: Siponen Mikko T. , Vartiainen Tero
Published: September 2007

Computer users copy computer software - this is well-known. However, less well-known are the reasons why some computer users choose to make unauthorized copies of computer software. Furthermore, the relationship linking the theory and the practice is unknown, i.e., how the attitudes of ordinary end-users correspond with the theoretical views of computer ethics scholars. In order to fill this gap in the literature, we investigated the moral attitudes of 249 Finnish computing students towards the unauthorized copying of computer software, and we then asked how these results compared with the theoretical reasons offered by computer ethics scholars. The results shed a new light on students' moral attitudes with respect to the unauthorized copying of software. In particular, this new knowledge is useful for computer ethics teachers, and for organizations seeking to combat this practice.
Anton, a special-purpose machine for molecular dynamics simulation
Authors: Shaw David E. , Deneroff Martin M. , Dror Ron O. , Kuskin Jeffrey S. , Larson Richard H. , Salmon John K. , Young Cliff , Batson Brannon , Bowers Kevin J. , Chao Jack C. , Eastwood Michael P. , Gagliardo Joseph , Grossman J. P. , Ho C. Richard , Ierardi Douglas J. , Kolossváry István , Klepeis John L. , Layman Timothy , McLeavey Christine , Moraes Mark A. , Mueller Rolf , Priest Edward C. , Shan Yibing , Spengler Jochen , Theobald Michael , Towles Brian , Wang Stanley C.
Published: September 2007

The ability to perform long, accurate molecular dynamics (MD) simulations involving proteins and other biological macro-molecules could in principle provide answers to some of the most important currently outstanding questions in the fields of biology, chemistry and medicine. A wide range of biologically interesting phenomena, however, occur over time scales on the order of a millisecond--about three orders of magnitude beyond the duration of the longest current MD simulations.

In this paper, we describe a massively parallel machine called Anton, which should be capable of executing millisecond-scale classical MD simulations of such biomolecular systems. The machine, which is scheduled for completion by the end of 2008, is based on 512 identical MD-specific ASICs that interact in a tightly coupled manner using a specialized high-speed communication network. Anton has been designed to use both novel parallel algorithms and special-purpose logic to dramatically accelerate those calculations that dominate the time required for a typical MD simulation. The remainder of the simulation algorithm is executed by a programmable portion of each chip that achieves a substantial degree of parallelism while preserving the flexibility necessary to accommodate anticipated advances in physical models and simulation methods.
Power provisioning for a warehouse-sized computer
Authors: Fan Xiaobo , Weber Wolf-Dietrich , Barroso Luiz Andre
Published: September 2007

Large-scale Internet services require a computing infrastructure that can beappropriately described as a warehouse-sized computing system. The cost ofbuilding datacenter facilities capable of delivering a given power capacity tosuch a computer can rival the recurring energy consumption costs themselves.Therefore, there are strong economic incentives to operate facilities as closeas possible to maximum capacity, so that the non-recurring facility costs canbe best amortized. That is difficult to achieve in practice because ofuncertainties in equipment power ratings and because power consumption tends tovary significantly with the actual computing activity. Effective powerprovisioning strategies are needed to determine how much computing equipmentcan be safely and efficiently hosted within a given power budget.

In this paper we present the aggregate power usage characteristics of largecollections of servers (up to 15 thousand) for different classes ofapplications over a period of approximately six months. Those observationsallow us to evaluate opportunities for maximizing the use of the deployed powercapacity of datacenters, and assess the risks of over-subscribing it. We findthat even in well-tuned applications there is a noticeable gap (7 - 16%)between achieved and theoretical aggregate peak power usage at the clusterlevel (thousands of servers). The gap grows to almost 40% in wholedatacenters. This headroom can be used to deploy additional compute equipmentwithin the same power budget with minimal risk of exceeding it. We use ourmodeling framework to estimate the potential of power management schemes toreduce peak power and energy usage. We find that the opportunities for powerand energy savings are significant, but greater at the cluster-level (thousandsof servers) than at the rack-level (tens). Finally we argue that systems needto be power efficient across the activity range, and not only at peakperformance levels.
Making the fast case common and the uncommon case simple in unbounded transactional memory
Authors: Blundell Colin , Devietti Joe , Lewis E. Christopher , Martin Milo M. K.
Published: September 2007

Hardware transactional memory has great potential to simplify the creation ofcorrect and efficient multithreaded programs, allowing programmers to exploitmore effectively the soon-to-be-ubiquitous multi-core designs. Several recentproposals have extended the original bounded transactional memory to unboundedtransactional memory, a crucial step toward transactions becoming ageneral-purpose primitive. Unfortunately, supporting the concurrent executionof an unbounded number of unbounded transactions is challenging, and as aresult, many proposed implementations are complex.

This paper explores a different approach. First, we introduce thepermissions-only cache to extend the bound at which transactions overflow toallow the fast, bounded case to be used as frequently as possible. Second, wepropose OneTM to simplify the implementation of unbounded transactional memoryby bounding the concurrency of transactions that overflow the cache. Thesemechanisms work synergistically to provide a simple and fast unboundedtransactional memory system.

The permissions-only cache efficiently maintains the coherencepermissions-but not data-for blocks read or written transactionally thathave been evicted from the processor's caches. By holding coherencepermissions for these blocks, the regular cache coherence protocol can be usedto detect transactional conflicts using only a few bits of on-chip storage peroverflowed cache block.OneTM allows only one overflowed transaction at a time, relying on thepermissions-only cache to ensure that overflow is infrequent. We present twoimplementations. In OneTM-Serialized, an overflowed transaction simply stallsall other threads in the application.

In OneTM-Concurrent, non-overflowedtransactions and non-transactional code can execute concurrently with theoverflowed transaction, providing more concurrency while retaining OneTM's coresimplifying assumption.
Synchronization state buffer
Authors: Zhu Weirong , Sreedhar Vugranam C , Hu Ziang , Gao Guang R.
Published: September 2007

Efficient fine-grain synchronization is extremely important to effectively harness the computational power of many-core architectures. However, designing and implementing finegrain synchronization in such architectures presents several challenges, including issues of synchronization induced overhead, storage cost, scalability, and the level of granularity to which synchronization is applicable. This paper proposes theSynchronization State Buffer(SSB), a scalable architectural design for fine-grain synchronization that efficiently performs synchronizations between concurrent threads. The design of SSB is motivated by the following observation:at any instance during the parallel execution only a small fraction of memory locations are actively participating in synchronization.Based on this observation we present a fine-grain synchronization design that records and manages the states of frequently synchronized data using modest hardware support. We have implemented the SSB design in the context of the 160-core IBM Cyclops-64 architecture. Using detailed simulation, we present our experience for a set of benchmarks with different workload characteristics.
Virtual hierarchies to support server consolidation
Authors: Marty Michael R. , Hill Mark D.
Published: September 2007

Server consolidation is becoming an increasingly popular
technique to manage and utilize systems. This paper develops CMP
memory systems for server consolidation where most sharing occurs
within Virtual Machines (VMs). Our memory systems maximize shared
memory accesses serviced within a VM, minimize interference among
separate VMs, facilitate dynamic reassignment of VMs to processors
and memory, and support content-based page sharing among VMs. We
begin with a tiled architecture where each of 64 tiles contains a
processor, private L1 caches, and an L2 bank. First, we reveal why
single-level directory designs fail to meet workload consolidation
goals. Second, we develop the paper's central idea of imposing a
two-level virtual (or logical) coherence hierarchy on a physically
flat CMP that harmonizes with VM assignment. Third, we show that
the best of our two virtual hierarchy (VH) variants performs 12-58%
better than the best alternative flat directory protocol when
consolidating Apache, OLTP, and Zeus commel workloads on our
simulated 64-core CMP.
An effective hybrid transactional memory system with strong isolation guarantees
Authors: Minh Chi Cao , Trautmann Martin , Chung JaeWoong , McDonald Austen , Bronson Nathan , Casper Jared , Kozyrakis Christos , Olukotun Kunle
Published: September 2007

We propose signature-accelerated transactional memory (SigTM), ahybrid TM system that reduces the overhead of software transactions. SigTM uses hardware signatures to track the read-set and write-set forpending transactions and perform conflict detection between concurrent threads. All other transactional functionality, including dataversioning, is implemented in software. Unlike previously proposed hybrid TM systems, SigTM requires no modifications to the hardware caches, which reduces hardware cost and simplifies support for nested transactions and multithreaded processor cores. SigTM is also the first hybrid TM system to provide strong isolation guarantees between transactional blocks and non-transactional accesses without additional read and write barriers in non-transactional code.

Using a set of parallel programs that make frequent use of coarse-grain transactions, we show that SigTM accelerates software transactions by 30% to 280%. For certain workloads, SigTM can match the performance of a full-featured hardware TM system, while for workloads with large read-sets it can be up to two times slower. Overall, we show that SigTM combines the performance characteristics and strong isolation guarantees of hardware TM implementations with the low cost and flexibility of software TM systems.
MetaTM/TxLinux
Authors: Ramadan Hany E. , Rossbach Christopher J. , Porter Donald E. , Hofmann Owen S. , Bhandari Aditya , Witchel Emmett
Published: September 2007

This paper quantifies the effect of architectural design decisions onthe performance of TxLinux. TxLinux is a Linux kernel modifiedto use transactions in place of locking primitives in several key subsystems.We run TxLinux on MetaTM, which is a new hardwaretransaction memory (HTM) model.MetaTM contains features that enable efficient and correct interrupthandling for an x86-like architecture.
Live stack overwrites
can corrupt non-transactional stack memory and requires a smallchange to the transaction register checkpoint hardware to ensurecorrect operation of the operating system. We also propose
stack based early release
to reduce spurious conflicts on stack memorybetween kernel code and interrupt handlers.We use MetaTM to examine the performance sensitivity of individualarchitectural features. For TxLinux we find that
Polka
and
SizeMatters
are effective contention management policies, someform of backoff on transaction contention is vital for performance,and stalling on a transaction conflict reduces transaction restartrates, but does not improve performance. Transaction write setsare small, and performance is insensitive to transaction abort costsbut sensitive to commit costs.
An integrated hardware-software approach to flexible transactional memory
Authors: Shriraman Arrvindh , Spear Michael F. , Hossain Hemayet , Marathe Virendra J. , Dwarkadas Sandhya , Scott Michael L.
Published: September 2007

There has been considerable recent interest in both hardware andsoftware transactional memory (TM). We present an intermediateapproach, in which hardware serves to accelerate a TM implementation controlled fundamentally by software. Specifically, we describe an alert on update mechanism (AOU) that allows a thread to receive fast, asynchronous notification when previously-identified lines are written by other threads, and a programmable data isolation mechanism (PDI) that allows a thread to hide its speculative writes from other threads, ignoring conflicts, until software decides to make them visible. These mechanisms reduce bookkeeping, validation, and copying overheads without constraining software policy on a host of design decisions.

We have used AOU and PDI to implement a hardwareacceleratedsoftware transactional memory system we call RTM. We have also used AOU alone to create a simpler "RTM-Lite". Across a range of microbenchmarks, RTM outperforms RSTM, a publicly available software transactional memory system, by as much as 8.7x (geometric mean of 3.5x) in single-thread mode. At 16 threads, it outperforms RSTM by as much as 5x, with an average speedup of 2x. Performance degrades gracefully when transactions overflow hardware structures. RTM-Lite is slightly faster than RTM for transactions that modify only small objects; full RTM is significantly faster when objects are large. In a strongargument for policy flexibility, we find that the choice between eager (first-access) and lazy (commit-time) conflict detection can lead to significant performance differences in both directions, depending on application characteristics.
Rotary router
Authors: Abad Pablo , Puente Valentin , Gregorio José Angel , Prieto Pablo
Published: September 2007

The trend towards increasing the number of processor cores and cache capacity in future Chip-Multiprocessors (CMPs), will require scalable packet-switched interconnection networks adapted to the restrictions imposed by the CMP environment. This paper presents an innovative router design, which successfully addresses CMP cost/performance constraints. The router structure is based on two independent rings, which force packets to circulate either clockwise or anti-clockwise, traveling through every port of the router. It uses a completely decentralized scheduling scheme, which allows the design to: (1) take advantage of wide links, (2) reduce Head of Line blocking, (3) use adaptive routing, (4) be topology agnostic, (5) scale with network degree, and (6) have reasonable power consumption and implementation cost. A thorough comparative performance analysis against competitive conventional routers shows an advantage for our proposal of up to 50 % in terms of raw performance and nearly 60 % in terms of energy-delay product.
Flattened butterfly
Authors: Kim John , Dally William J. , Abts Dennis
Published: September 2007

Increasing integrated-circuit pin bandwidth has motivateda corresponding increase in the degree or radix of interconnection networksand their routers. This paper introduces the
flattened butterfly,
a cost-efficient topology for high-radix networks. On benign (load-balanced) traffic, the flattened butterfly approaches the cost/performance of a butterfly network and has roughly half the cost of a comparable performance Clos network.The advantage over the Clos is achieved by eliminating redundant hopswhen they are not needed for load balance. On adversarial traffic, the flattened butterfly matches the cost/performance of a folded-Clos network and provides an order of magnitude better performance than a conventional butterfly.In this case, global adaptive routing is used to switchthe flattened butterfly from minimal to non-minimal routing - usingredundant hops only when they are needed. Minimal and non-minimal, oblivious and adaptive routing algorithms are evaluated on the flattened butterfly.We show that load-balancing adversarial traffic requires non-minimalglobally-adaptive routing and show that
sequential
allocators are required to avoid transient load imbalance when using adaptive routing algorithms.We also compare the cost of the flattened butterfly to folded-Clos, hypercube,and butterfly networks with identical capacityand show that the flattened butterfly is more cost-efficient thanfolded-Clos and hypercube topologies.
A novel dimensionally-decomposed router for on-chip communication in 3D architectures
Authors: Kim Jongman , Nicopoulos Chrysostomos , Park Dongkook , Das Reetuparna , Xie Yuan , Narayanan Vijaykrishnan , Yousif Mazin S. , Das Chita R.
Published: September 2007

Much like multi-storey buildings in densely packed metropolises, three-dimensional (3D) chip structures are envisioned as a viable solution to skyrocketing transistor densities and burgeoning die sizes in multi-core architectures. Partitioning a larger die into smaller segments and then stacking them in a 3D fashion can significantly reduce latency and energy consumption. Such benefits emanate from the notion that inter-wafer distances are negligible compared to intra-wafer distances. This attribute substantially reduces global wiring length in 3D chips. The work in this paper integrates the increasingly popular idea of packet-based Networks-on-Chip (NoC) into a 3D setting. While NoCs have been studied extensively in the 2D realm, the microarchitectural ramifications of moving into the third dimension have yet to be fully explored. This paper presents a detailed exploration of inter-strata communication architectures in 3D NoCs. Three design options are investigated; a simple bus-based inter-wafer connection, a hop-by-hop standard 3D design, and a full 3D crossbar implementation. In this context, we propose a novel partially-connected 3D crossbar structure, called the 3D Dimensionally-Decomposed (DimDe) Router, which provides a good tradeoff between circuit complexity and performance benefits. Simulation results using (a) a stand-alone cycle-accurate 3D NoC simulator running synthetic workloads, and (b) a hybrid 3D NoC/cache simulation environment running real commercial and scientific benchmarks, indicate that the proposed DimDe design provides latency and throughput improvements of over 20% on average over the other 3D architectures, while remaining within 5% of the full 3D crossbar performance. Furthermore, based on synthesized hardware implementations in 90 nm technology, the DimDe architecture outperforms all other designs -- including the full 3D crossbar -- by an average of 26% in terms of the Energy-Delay Product (EDP).
Express virtual channels
Authors: Kumar Amit , Peh Li-Shiuan , Kundu Partha , Jha Niraj K.
Published: September 2007

Due to wire delay scalability and bandwidth limitations inherent in shared buses and dedicated links, packet-switched on-chip interconnection networks are fast emerging as the pervasive communication fabric to connect different processing elements in many-core chips. However, current state-of-the-art packet-switched networks rely on complex routers which increases the communication overhead and energy consumption as compared to the ideal interconnection fabric.

In this paper, we try to close the gap between the state-of-the-art packet-switched network and the ideal interconnect by proposing express virtual channels (EVCs), a novel flow control mechanism which allows packets to virtually bypass intermediate routers along their path in a completely non-speculative fashion, thereby lowering the energy/delay towards that of a dedicated wire while simultaneously approaching ideal throughput with a practical design suitable for on-chip networks.

Our evaluation results using a detailed cycle-accurate simulator on a range of synthetic traffic and SPLASH benchmark traces show upto 84% reduction in packet latency and upto 23% improvement in throughput while reducing the average router energy consumption by upto 38% over an existing state-of-the-art packet-switched design. When compared to the ideal interconnect, EVCs add just two cycles to the no-load latency, and are within 14% of the ideal throughput. Moreover, we show that the proposed design incurs a minimal hardware overhead while exhibiting excellent scalability with increasing network sizes.
Hardware atomicity for reliable software speculation
Authors: Neelakantam Naveen , Rajwar Ravi , Srinivas Suresh , Srinivasan Uma , Zilles Craig
Published: September 2007

Speculative compiler optimizations are effective in improving both single-thread performance and reducing power consumption, but their implementation introduces significant complexity, which can limit their adoption, limit their optimization scope, and negatively impact the reliability of the compilers that implement them. To eliminate much of this complexity, as well as increase the effectiveness of these optimizations, we propose that microprocessors provide architecturally-visible hardware primitives for atomic execution. These primitives provide to the compiler the ability to optimize the program's hot path in isolation, allowing the use of non-speculative formulations of optimization passes to perform speculative optimizations. Atomic execution guarantees that if a speculation invariant does not hold, the speculative updates are discarded, the register state is restored, and control is transferred to a non-speculative version of the code, thereby relieving the compiler from the responsibility of generating compensation code.

We demonstrate the benefit of hardware atomicity in the context of a Java virtual machine. We find incorporating the notion of atomic regions into an existing compiler intermediate representation to be natural, requiring roughly 3,000 lines of code (~3% of a JVM's optimizing compiler), most of which were for region formation. Its incorporation creates new opportunities for existing optimization passes, as well as greatly simplifying the implementation of additional optimizations (e.g., partial inlining, partial loop unrolling, and speculative lock elision). These optimizations reduce dynamic instruction count by 11% on average and result in a 10-15% average speedup, relative to a baseline compiler with a similar degree of inlining.
Core fusion
Authors: Ipek Engin , Kirman Meyrem , Kirman Nevin , Martinez Jose F.
Published: September 2007

This paper presents
core fusion,
a reconfigurable chip multiprocessor(CMP) architecture where groups of fundamentally independent cores can dynamically morph into a larger CPU, or they can be used as distinct processing elements, as needed at run time by applications. Core fusion gracefully accommodates software diversity and incremental parallelization in CMPs. It provides a single execution model across all configurations, requires no additional programming effort or specialized compiler support, maintains ISA compatibility, and leverages mature micro-architecture technology.