bluuebunny/crossref_metadata_2025 huggingface dataset:
Virtual ring routing
Authors: Caesar Matthew , Castro Miguel , Nightingale Edmund B. , O'Shea Greg , Rowstron Antony
Published: October 2006

This paper presents Virtual Ring Routing (VRR), a new network routing protocol that occupies a unique point in the design space. VRR is inspired by overlay routing algorithms in Distributed Hash Tables (DHTs) but it does not rely on an underlying network routing protocol. It is implemented directly on top of the link layer. VRR provides both raditional point-to-point network routing and DHT routing to the node responsible for a hash table key.VRR can be used with any link layer technology but this paper describes a design and several implementations of VRR that are tuned for wireless networks. We evaluate the performance of VRR using simulations and measurements from a sensor network and an 802.11a testbed. The experimental results show that VRR provides robust performance across a wide range of environments and workloads. It performs comparably to, or better than, the best wireless routing protocol in each experiment. VRR performs well because of its unique features: it does not require network flooding or trans-lation between fixed identifiers and location-dependent addresses.
Trusted computing
Authors: Weiss Aaron
Published: October 2006

Will the open, unrestricted PC soon become a thing of the past?
Long-latency branches
Authors: Kumar Abhas , Jain Nisheet , Chaudhuri Mainak
Published: October 2006

Dynamic branch prediction plays a key role in delivering high performance in the modern microprocessors. The cycles between the prediction of a branch and its execution constitute the branch misprediction penalty because a misprediction can be detected only after the branch executes. Branch misprediction penalty depends not only on the depth of the pipeline, but also on the availability of branch operands. Fetched branches belonging to the dependence chains of loads that miss in the L1 data cache exhibit very high misprediction penalty due to the delay in the execution resulting from unavailability of operands. We call these the
long-latency branches.
It has been speculated that predicting such branches accurately or identifying such mispredicted branches before they execute would be beneficial. In this paper, we show that in a traditional pipeline the frequency of mispredicted long-latency branches is extremely small. Therefore, predicting all these branches correctly does not offer any performance improvement. Architectures that allow checkpoint-assisted speculative load retirement fetch a large number of branches belonging to the dependence chains of the speculatively retired loads. Accurate prediction of these branches is extremely important for staying on the correct path. We show that even if
all
the branches belonging to the dependence chains of the loads that miss in the L1 data cache are predicted correctly, only four applications out of twelve control speculation-sensitive applications selected from the SPECInt2000 and BioBench suites exhibit visible performance improvement. This is an upper bound on the achievable performance improvement in these architectures. This article concludes that it may not be worth designing specialized hardware to improve the prediction accuracy of the long-latency branches.
An algebraic array shape inference system for MATLAB®
Authors: Joisha Pramod G. , Banerjee Prithviraj
Published: October 2006

The problem of inferring array shapes ahead of time in languages that exhibit both implicit and dynamic typing is a critical one because the ramifications of its solution are the better organization of array storage through compaction and reuse, and the generation of high-performance code through specialization by shape. This article addresses the problem in a prototypical implicitly and dynamically typed array language called MATLAB. The approach involves modeling the language's shape semantics using an algebraic system, and applying term rewriting techniques to evaluate expressions under this algebra. Unlike prior efforts at array shape determination, this enables the deduction of valuable shape information even when array extents are compile-time unknowns. Furthermore, unlike some previous methods, our approach doesn't impose monotonicity requirements on an operator's shape semantics. The work also describes an inference methodology and reports measurements from a type inference engine called MAGICA. In a benchmark suite of 17 programs, the shape inference subsystem in MAGICA detected the equivalence of over 61% of the symbolic shapes in six programs, and over 57% and 37% of the symbolic shapes in two others. In the remaining nine programs, all array shapes were inferred to be compile-time constants.
The register function for
t
-ary trees
Authors: Drmota Michael , Prodinger Helmut
Published: October 2006

For the register function for
t
-ary trees, recently introduced by Auber et al., we prove that the average is log
4
n
+
O
(1), if all such trees with
n
internal nodes are considered to be equally likely.This result remains true for rooted trees where the set of possible out-degrees is finite. Furthermore we obtain exponential tail estimates for the distribution of the register function. Thus, the distribution is highly concentrated around the mean value.
Online topological ordering
Authors: Katriel Irit , Bodlaender Hans L.
Published: October 2006

It is shown that the problem of maintaining the topological order of the nodes of a directed acyclic graph while inserting
m
edges can be solved in
O
(min{
m
3/2
log
n
,
m
3/2
+
n
2
log
n
}) time, an improvement over the best known result of
O
(
mn
). In addition, we analyze the complexity of the same algorithm with respect to the treewidth
k
of the underlying undirected graph. We show that the algorithm runs in time
O
(
mk
log
2
n
) for general
k
and that it can be implemented to run in
O
(
n
log
n
) time on trees, which is optimal. The algorithm also detects cycles in the input.
Optimal constrained graph exploration
Authors: Duncan Christian A. , Kobourov Stephen G. , Kumar V. S. Anil
Published: October 2006

We address the problem of constrained exploration of an unknown graph
G
= (
V
,
E
) from a given start node
s
with either a tethered robot or a robot with a fuel tank of limited capacity, the former being a tighter constraint. In both variations of the problem, the robot can only move along the edges of the graph, for example, it cannot jump between nonadjacent nodes. In the tethered robot case, if the tether (rope) has length
l
, then the robot must remain within distance
l
from the start node
s
. In the second variation, a fuel tank of limited capacity forces the robot to return to
s
after traversing
C
edges. The efficiency of algorithms for both variations of the problem is measured by the number of edges traversed during the exploration. We present an algorithm for a tethered robot that explores the graph in Θ(|
E
|) edge traversals. The problem of exploration using a robot with a limited fuel tank capacity can be solved with a simple reduction from the tethered robot case and also yields a Θ(|
E
|) algorithm. This improves on the previous best-known bound of
O
(|
E
| + |
V
|log
2
|
V
|). Since the lower bound for the graph exploration problems is Ω(|
E
|), our algorithm is optimal within a constant factor.
Faster fixed parameter tractable algorithms for finding feedback vertex sets
Authors: Raman Venkatesh , Saurabh Saket , Subramanian C. R.
Published: October 2006

A feedback vertex set (
fvs
) of a graph is a set of vertices whose removal results in an acyclic graph. We show that if an undirected graph on
n
vertices with minimum degree at least 3 has a fvs on at most 1/3
n
1 − ϵ
vertices, then there is a cycle of length at most 6/ϵ (for ϵ ≥ 1/2, we can even improve this to just 6).Using this, we obtain a
O
((12 log
k
/log log
k
+ 6)
k
n
ω
algorithm for testing whether an undirected graph on
n
vertices has a fvs of size at most
k
. Here
n
ω
is the complexity of the best matrix multiplication algorithm. The previous best parameterized algorithm for this problem took
O
((2
k
+ 1)

k

n
2
) time.We also investigate the fixed parameter complexity of weighted feedback vertex set problem in weighted undirected graphs.
Embedded systems in the wild
Authors: Martonosi Margaret
Published: October 2006

The Princeton ZebraNet project is a collaboration of engineers and biologists to build mobile, wireless embedded systems for wildlife tracking. Over the lifetime of the project, we have implemented a number of compression, communication, and data management algorithms specifically tailored for the small memory, constrained energy and sparse connectivity of these long-lifetime systems. We have gone through three major generations of hardware and software implementations, and have done two successful real-world deployments on Plains Zebras in Kenya, with a third deployment planned for Summer, 2007. In this talk, I will discuss our real-life experiences with crafting embedded systems hardware and software, and our deployment experiences in Africa. I will also put forward a vision for how portability, reliability, and energy-efficiency can be well-supported in future embedded systems.
Clarifying the role of self-efficacy and metacognition as predictors of performance
Authors: Moores Trevor T. , Chang Jerry Cha-Jan , Smith Deborah K.
Published: October 2006

We propose extending our understanding of self-efficacy by comparing self-efficacy with a related construct called metacognition. Metacognition involves the monitoring and control of one's thought processes and is often related, as is self-efficacy, to performance on a task. We develop an instrument that attempts to measure both self-efficacy and metacognition with respect to one's performance on a test covering declarative and procedural knowledge (knowing that, and knowing how) of DFDs and ERDs. With data collected from a sample of 124 students, we use partial least squares (PLS) to show that self-efficacy and metacognition are distinct yet related constructs. While self-efficacy is a predictor of both declarative and procedural knowledge, metacognition is only related to procedural knowledge. We discuss the implications of these results and suggest further research is needed to compare and contrast the role of these constructs in assessing learning outcomes.
IT worker turnover
Authors: Thatcher Jason Bennett , Liu Yongmei , Stepina Lee P. , Goodman Joseph M. , Treadway Darren C.
Published: October 2006

This study examined intrinsic motivation's influence on information technology (IT) workers' attitudes and intentions. Drawing on Human Resource management research (Eby & Freeman, 1999), we model Intrinsic motivation as mediating the influence of motivators (i.e., intrinsic job characteristics) and hygiene factors (i.e., pay and supervisory satisfaction) on workplace attitudes (i.e., job satisfaction and affective organizational commitment). In turn, workplace attitudes mediate the influence of intrinsic motivation on turnover intention. The model was tested using data collected from public sector IT workers in the Southeastern United States. Although intrinsic motivation did not fully mediate the influence of motivators and hygiene factors, findings suggest that intrinsic motivation positively influences workplace attitudes and has a mediated influence on turnover intent. Implications for research and practice are offered.
Cohesion in virtual teams
Authors: Salisbury Wm. David , Carte Traci A. , Chidambaram Laku
Published: October 2006

With the advent of new technology-enabled organizational forms, firms are increasingly relying on virtual teams to accomplish organizational objectives. For those studying these environments, sound measurement of work team phenomena, such as group cohesion, is the key to understanding the impact of these new technologies on team processes and performance. Bollen and Hoyle (1990) created a six-item Perceived Cohesion Scale (PCS) to measure cohesion in groups and employed a study of large groups to assess the psychometric qualities of their scale. Chin et al. (1999) validated the PCS measure using a study of small groups that were collocated. The present effort extends the Chin et al. (1999) adaptation of Bollen and Hoyle's PCS scale to virtual teams and attempts to validate it in this setting. Our findings indicate support for the validity, reliability and factorial stability of the measure in this virtual team context.
Enhancing customer value through IT investments
Authors: Dow Kevin E. , Hackbarth Gary , Wong Jeff
Published: October 2006

The Net-Enabled Business Innovation Cycle (NEBIC) is a holistic theory that describes a pathway firms may use to leverage net-enablement. We assert that the strategic information system role constructs used in past studies are related to the stages found in the NEBIC. This suggests that information technology announcement studies should consider the role of net-enablement in creating customer value. We use the event study methodology to test the market's reaction to 298 announcements of technology investments that correspond to different information technology role constructs and the related NEBIC stages. Our findings suggest that customer value is added to firms through the value creation process described by the NEBIC.
Fast and accurate algorithms for protein side-chain packing
Authors: Xu Jinbo , Berger Bonnie
Published: October 2006

This article studies the protein side-chain packing problem using the tree-decomposition of a protein structure. To obtain fast and accurate protein side-chain packing, protein structures are modeled using a geometric neighborhood graph, which can be easily decomposed into smaller blocks. Therefore, the side-chain assignment of the whole protein can be assembled from the assignment of the small blocks. Although we will show that the side-chain packing problem is stillNP-hard, we can achieve a tree-decomposition-based globally optimal algorithm with time complexity ofO(Nnrottw+ 1)and several polynomial-time approximation schemes (PTAS), whereNis the number of residues contained in the protein,nrotthe average number of rotamers for each residue, andtw=O(N2/3logN) the treewidth of the protein structure graph. Experimental results indicate that after Goldstein dead-end elimination is conducted,nrotis very small andtwis equal to 3 or 4 most of the time. Based on the globally optimal algorithm, we developed a protein side-chain assignment program TreePack, which runs up to 90 times faster than SCWRL 3.0, a widely-used side-chain packing program, on some large test proteins in the SCWRL benchmark database and an average of five times faster on all the test proteins in this database. There are also some real-world instances that TreePack can solve but that SCWRL 3.0 cannot. The TreePack program is available at http://ttic.uchicago.edu/~jinbo/TreePack.htm.
Individualized exercises for self-assessment of programming knowledge
Authors: Brusilovsky Peter , Sosnovsky Sergey
Published: October 2006

Individualized exercises are a promising feature in promoting modern e-learning. The focus of this article is on the QuizPACK system, which is able to generate parameterized exercises for the C language and automatically evaluate the correctness of student answers. We introduce QuizPACK and present the results of its comprehensive classroom evaluation during four consecutive semesters. Our studies demonstrate that when QuizPACK is used for out-of-class self-assessment, it is an exceptional learning tool. The students' work with QuizPACK significantly improved their knowledge of semantics and positively affected higher-level knowledge and skills. The students themselves praised the system highly as a learning tool. We also demonstrated that the use of the system in self-assessment mode can be significantly increased by basing later classroom paper-and-pencil quizzes on QuizPACK questions, motivating students to practice them more.
Report on the International Workshop on Service Oriented Software Engineering (IW-SOSE06)
Authors: Di Nitto Elisabetta , Hall Robert J. , Han Jun , Han Yanbo , Polini Andrea , Sandkuhl Kurt , Zisman Andrea
Published: October 2006

This paper presents a report of the International Workshop on Service Oriented Software Engineering colocated with ICSE2006. In particular, we shortly present the papers that have been accepted for publication in the workshop proceedings, the keynote speech, and the discussion topics that have emerged during the workshop.
5th Intl. Workshop on Scenarios and State Machines
Authors: Whittle Jon , Geiger Leif , Meisinger Michael
Published: October 2006

SCESM'06 was the 5th International Workshop on Scenarios and State Machines: Models, Algorithms and Tools. It was a one day ICSE'06 workshop taking place on May 27, 2006. Details about SCESM'06 may be found at http://ise.gmu.edu/scesm06/.
Approaches to aspect oriented design
Authors: Dahiya Deepak , Sachdeva Rajinder K.
Published: October 2006

There is a need to study various approaches in the use of object-oriented design patterns and aspect oriented design approach in enterprise systems for architecture and its implementation. The development of aspect oriented requirements gathering approach, design notation and environment for development of enterprise systems needs to be further refined in the context of software applications and industry. Current development in aspects and the path to future work in this direction is highlighted regarding developing a general-purpose design language for aspect oriented software development.
A practical extension to the VORD model
Authors: Rekoske Jeffrey , Ghasemiyeh Hamid , Salem Ahmed
Published: October 2006

This paper describes an extension to the VORD model and attempts to resolve its lack of direct support for viewpoint interaction. Supporting the viewpoint interaction provides a useful tool for analyzing requirements changes and automating systems. It can also be used to indicate when multiple requirements are specified as a single requirement. The extension is demonstrated with the bank auto-teller system that was part of the original VORD proposal.
Troubleshooting wireless mesh networks
Authors: Qiu Lili , Bahl Paramvir , Rao Ananth , Zhou Lidong
Published: October 2006

Effective network troubleshooting is critical for maintaining efficient and reliable network operation. Troubleshooting is especially challenging in multi-hop wireless networks because the behavior of such networks depends on complicated interactions between many factors such as RF noise, signal propagation, node interference, and traffic flows. In this paper we propose a new direction for research on fault diagnosis in wireless mesh networks. Specifically, we present a diagnostic system that employs trace-driven simulations to detect faults and perform root cause analysis. We apply this approach to diagnose performance problems caused by packet dropping, link congestion, external noise, and MAC misbehavior. In a 25 node mesh network, we are able to diagnose over 10 simultaneous faults of multiple types with more than 80% coverage.
NetScale
Authors: Fournié Laurent , Hong Dohy , Perisse Florent
Published: October 2006

This paper presents a scalable time-stepped hybrid simulation algorithm which is well adapted to the simulation of large IP networks (up to one million of competing ows and network elements), while tracking reactive traffic behaviour and packet-level phenomena e.g. timeout trigger or packet burstiness. This simulation paradigm allows one to gain several orders of magnitude of computation time compared to traditional discrete event simulation approaches. The accuracy of this simulation method is evaluated by comparison to other simulation methodologies. Examples of large scale network simulations are also presented.
Update on buffer sizing in internet routers
Authors: Ganjali Yashar , McKeown Nick
Published: October 2006

In the past two years, several papers have proposed rules that suggest two to five orders of magnitude reduction in Internet core router buffers. Others present scenarios where buffer sizes need to be significantly increased. So why the different rules? In this paper we briefly compare the different results and proposals, and summarize some recent preliminary experiments to validate the proposals. We'll see that different results apply to different parts of the network, and depend on several assumptions. For example, we believe that buffers can be safely reduced by an order of magnitude in the routers in service provider backbone networks; but it would be premature to reduce them in routers closer to the edge.
What makes a good programmer?
Authors: Cegielski Casey G. , Hall Dianne J.
Published: October 2006

An examination of the relationship of values, cognitive ability, and personality as predictors of object-oriented programming performance.
Ambidextrous coping strategies in globally distributed software development projects
Authors: Lee Gwanhoo , DeLone William , Espinosa J. Alberto
Published: October 2006

Strategies for enhancing flexibility and rigor.
Aligning IT components to achieve agility in globally distributed system development
Authors: Lee One-Ki (Daniel) , Banerjee Probir , Lim Kai H. , Kumar Kuldeep , Hillegersberg Jos van , Wei Kwok Kee
Published: October 2006

Agile IT strategy, infrastructure, and project management are key elements for realizing agility in GDSD projects.
Terra
Authors: Garfinkel Tal , Pfaff Ben , Chow Jim , Rosenblum Mendel , Boneh Dan
Published: October 2006

We present a flexible architecture for trusted computing, called Terra, that allows applications with a wide range of security requirements to run simultaneously on commodity hardware. Applications on Terra enjoy the semantics of running on a separate, dedicated, tamper-resistant hardware platform, while retaining the ability to run side-by-side with normal applications on a general-purpose computing platform. Terra achieves this synthesis by use of a
trusted virtual machine monitor
(TVMM) that partitions a tamper-resistant hardware platform into multiple, isolated virtual machines (VM), providing the appearance of multiple boxes on a single, general-purpose platform. To each VM, the TVMM provides the semantics of either an "open box," i.e. a general-purpose hardware platform like today's PCs and workstations, or a "closed box," an opaque special-purpose platform that protects the privacy and integrity of its contents like today's game consoles and cellular phones. The software stack in each VM can be tailored from the hardware interface up to meet the security requirements of its application(s). The hardware and TVMM can act as a trusted party to allow closed-box VMs to cryptographically identify the software they run, i.e. what is in the box, to remote parties. We explore the strengths and limitations of this architecture by describing our prototype implementation and several applications that we developed for it.
Separating agreement from execution for byzantine fault tolerant services
Authors: Yin Jian , Martin Jean-Philippe , Venkataramani Arun , Alvisi Lorenzo , Dahlin Mike
Published: October 2006

We describe a new architecture for Byzantine fault tolerant state machine replication that separates
agreement
that orders requests from
execution
that processes requests. This separation yields two fundamental and practically significant advantages over previous architectures. First, it reduces replication costs because the new architecture can tolerate faults in up to half of the state machine replicas that execute requests. Previous systems can tolerate faults in at most a third of the combined agreement/state machine replicas. Second, separating agreement from execution allows a general
privacy firewall
architecture to protect confidentiality through replication. In contrast, replication in previous systems hurts confidentiality because exploiting the weakest replica can be sufficient to compromise the system. We have constructed a prototype and evaluated it running both microbenchmarks and an NFS server. Overall, we find that the architecture adds modest latencies to unreplicated systems and that its performance is competitive with existing Byzantine fault tolerant systems.
Bullet
Authors: Kostić Dejan , Rodriguez Adolfo , Albrecht Jeannie , Vahdat Amin
Published: October 2006

In recent years, overlay networks have become an effective alternative to IP multicast for efficient point to multipoint communication across the Internet. Typically, nodes self-organize with the goal of forming an efficient overlay tree, one that meets performance targets without placing undue burden on the underlying network. In this paper, we target high-bandwidth data distribution from a single source to a large number of receivers. Applications include large-file transfers and real-time multimedia streaming. For these applications, we argue that an overlay
mesh
, rather than a tree, can deliver fundamentally higher bandwidth and reliability relative to typical tree structures. This paper presents
Bullet
, a scalable and distributed algorithm that enables nodes spread across the Internet to self-organize into a high bandwidth overlay mesh. We construct Bullet around the insight that data should be distributed in a disjoint manner to strategic points in the network. Individual Bullet receivers are then responsible for locating and retrieving the data from multiple points in parallel.Key contributions of this work include: i) an algorithm that sends data to different points in the overlay such that any data object is equally likely to appear at any node, ii) a scalable and decentralized algorithm that allows nodes to locate and recover missing data items, and iii) a complete implementation and evaluation of Bullet running across the Internet and in a large-scale emulation environment reveals up to a factor two bandwidth improvements under a variety of circumstances. In addition, we find that, relative to tree-based solutions, Bullet reduces the need to perform expensive bandwidth probing. In a tree, it is critical that a node's parent delivers a high rate of application data to each child. In Bullet however, nodes simultaneously receive data from multiple sources in parallel, making it less important to locate any single source capable of sustaining a high transmission rate.
SplitStream
Authors: Castro Miguel , Druschel Peter , Kermarrec Anne-Marie , Nandi Animesh , Rowstron Antony , Singh Atul
Published: October 2006

In tree-based multicast systems, a relatively small number of interior nodes carry the load of forwarding multicast messages. This works well when the interior nodes are highly-available, dedicated infrastructure routers but it poses a problem for application-level multicast in peer-to-peer systems. SplitStream addresses this problem by striping the content across a forest of interior-node-disjoint multicast trees that distributes the forwarding load among all participating peers. For example, it is possible to construct efficient SplitStream forests in which each peer contributes only as much forwarding bandwidth as it receives. Furthermore, with appropriate content encodings, SplitStream is highly robust to failures because a node failure causes the loss of a single stripe on average. We present the design and implementation of SplitStream and show experimental results obtained on an Internet testbed and via large-scale network simulation. The results show that SplitStream distributes the forwarding load among all peers and can accommodate peers with different bandwidth capacities while imposing low overhead for forest construction and maintenance.
SIGACT news complexity theory column 52
Authors: Hemaspaandra Lane A.
Published: October 2006

For those who are big fans of the fantastic complexity textbook by Daniel Bovet and Pierluigi Crescenzi [BC93] (and I myself certainly am), there is great news. The authors have made their book available online, free of charge for noncommercial use. It can be found at via Pilu's web site (start at http://www.algoritmica.org/piluc, then click on the "Books" section, and then click on "Introduction to the Theory of Complexity").
Want scalable computing?
Authors: Keidar Idit , Schuster Assaf
Published: October 2006

Distributed computing is currently undergoing a paradigm shift, towards large-scale dynamic systems, where thousands of nodes collaboratively solve computational tasks. Examples of such emerging systems include autonomous sensor networks, data-grids, wireless mesh network (WMN) infrastructures, and more. We argue that speculative computations will be instrumental to successfully performing meaningful computations in such systems. Moreover, solutions deployed in such platforms will need to be as local as possible.
Security and composition of cryptographic protocols
Authors: Canetti Ran
Published: October 2006

What does it mean for a cryptographic protocol to be "secure"? Capturing the security requirements of cryptographic tasks in a meaningful way is a slippery business: On the one hand, we want security criteria that prevent "all potential attacks" against a protocol; on the other hand, we want our criteria not to be overly restrictive and accept "reasonable protocols". One of the main reasons for flaws is the often unexpected interactions among different protocol instances that run alongside each other in a composite system.This tutorial studies a general methodology for defining security of cryptographic protocols. The methodology, often dubbed the "trusted party paradigm", allows for defining the security requirements of a large variety of cryptographic tasks in a unified and natural way. We first review more basic formulations that capture security in isolation from other protocol instances. Next we address the security problems associated with protocol composition, and review formulations that guarantee security even in composite systems.
Comparing Java, C# and Ada monitors queuing policies
Authors: Kaiser Claude , Pradat-Peyre Jean-François , Évangelista Sami , Rousseau Pierre
Published: October 2006

Learning concurrency paradigms is necessary but it is not sufficient since the choice of run-time semantics may introduce subtle programming errors. It is the aim of this paper to exemplify the importance of process queuing and awaking policies resulting from possible choices of the monitor concept implementation.The first part of the paper compares the behaviour of concurrent processes sharing a unique waiting queue for condition synchronization when implemented in Java or in Ada. A particular solution of the dining philosophers paradigm will be used to show how the difference in the monitor semantics may lead or not to deadlock. This comparison provides insight for deriving a correct Java implementation. The second part of the paper shows how the implementation can be refined when using Ada entry families and requeue with requeue once restriction. The result is elegant, safe and fair, and deterministic. This paper ends with quantitative comparisons of concurrency complexity and of concurrency effectiveness.We conclude that Java and C# multithreading need defensive concurrent programming while Ada allows more latitude for developing correct concurrent programs.
Saddle Up, Aspiring Code Jockeys
Authors: Neville-Neil George
Published: October 2006

Dear KV, I am an IT consultant/contractor. I work mainly on networks and Microsoft operating systems. I have been doing this work for more than eight years. Unfortunately, it is starting to bore me. My question is: How would I go about getting back into programming? I say getting back into because I have some experience. In high school I took two classes of programming in Applesoft BASIC. I loved it, aced everything, and was the best programming student the teacher ever saw. This boosted my interest in computer science, which I pursued in college. In college, I took classes in C++, Java, and Web development. I did great and had fun. For various reasons, I ended up leaving college and becoming a network administrator, and for the past eight years have been doing this and that and everything else IT-related. But I haven’t been programming. The extent of my programming work experience is with MS Excel macros and basic VB coding in Microsoft Access. So how could I start becoming a programmer? Visual Studio 2005? Java? Eclipse? I enjoy self-learning and have found that achieving certifications gets my foot in the door. Is there a particular suite that I could get certified in to get my newly desired career going?
You Can Look It Up: or Maybe Not
Authors: Kelly-Bootle Stan
Published: October 2006

Many are said to have said, "If I can’t take it with me, I’m not going!" I’ve just said it, but that hardly counts. Who, we demand, said or wrote it first? It’s what I call (and claim first rights on) a FUQ (frequently unanswerable question, pronounced fook to avoid ambiguity and altercation). Yogi Berra’s famous advice was "You can look it up," meaning, in fact, "Take my word on this." He knew quite well that few had the means or patience to wade through the records. Nowadays, of course, as we quip in Unix, it’s easier done than sed.
Extraction of coherent relevant passages using hidden Markov models
Authors: Jiang Jing , Zhai Chengxiang
Published: October 2006

In information retrieval, retrieving relevant passages, as opposed to whole documents, not only directly benefits the end user by filtering out the irrelevant information within a long relevant document, but also improves retrieval accuracy in general. A critical problem in passage retrieval is to extract
coherent relevant passages
accurately from a document, which we refer to as
passage extraction
. While much work has been done on passage retrieval, the passage extraction problem has not been seriously studied. Most existing work tends to rely on presegmenting documents into fixed-length passages which are unlikely optimal because the length of a relevant passage is presumably highly sensitive to both the query and document.In this article, we present a new method for accurately detecting coherent relevant passages of variable lengths using hidden Markov models (HMMs). The HMM-based method naturally captures the topical boundaries between passages relevant and nonrelevant to the query. Pseudo-feedback mechanisms can be naturally incorporated into such an HMM-based framework to improve parameter estimation. We show that with appropriate parameter estimation, the HMM method outperforms a number of strong baseline methods on two datasets. We further show how the HMM method can be applied on top of any basic passage extraction method to improve passage boundaries.
Energy-efficient, utility accrual scheduling under resource constraints for mobile embedded systems
Authors: Wu Haisang , Ravindran Binoy , Jensen E. Douglas , Li Peng
Published: October 2006

We present an energy-efficient, utility accrual, real-time scheduling algorithm called ReUA. ReUA considers an application model where activities are subject to time/utility function time constraints, mutual exclusion constraints on shared non-CPU resources, and statistical performance requirements on individual activity timeliness behavior. The algorithm targets mobile embedded systems where
system-level
energy consumption is also a major concern. For such a model, we consider the scheduling objectives of (1) satisfying the statistical performance requirements and (2) maximizing the system-level energy efficiency, while respecting resource constraints. Since the problem is NP-hard, ReUA allocates CPU cycles using statistical properties of application cycle demands, and heuristically computes schedules with a polynomial time cost. We analytically establish several timeliness and nontimeliness properties of the algorithm. Further, our simulation experiments illustrate ReUA's effectiveness and superiority.
Parallelizing load/stores on dual-bank memory embedded processors
Authors: Zhuang Xiaotong , Pande Santosh
Published: October 2006

Many modern embedded processors such as DSPs support partitioned memory banks (also called X--Y memory or dual-bank memory) along with parallel load/store instructions to achieve higher code density and performance. In order to effectively utilize the parallel load/store instructions, the compiler must partition the memory-resident values and assign them to X or Y bank. This paper gives a postregister allocation solution to merge the generated load/store instructions into their parallel counterparts. Simultaneously, our framework performs allocation of values to X or Y memory banks. We first remove as many load/stores and register--register moves as possible through an excellent iterated coalescing based register allocator by Appel and George [1996]. We then attempt to parallelize the generated load/stores using a multipass approach. The basic phase of our approach attempts the merger of load/stores without duplication and web splitting. We model this problem as a graph-coloring problem in which each value is colored as either X or Y. We then construct a motion scheduling graph (MSG), based on the range of motion for each load/store instruction. MSG reflects potential instructions that could be merged. We propose a notion of pseudofixed boundaries so that the load/store movement is less affected by register dependencies. We prove that the coloring problem for MSG is NP-complete and solve it with two different heuristic algorithms with different complexity. We then propose a two-level iterative process to attempt instruction duplication, variable duplication, web splitting, and local conflict elimination to effectively merge the remaining load/stores. Finally, we clean up some multiple-aliased load/stores. To improve the performance, we combine profiling information with each stage coupled with some modifications to the algorithm. We show that our framework results in parallelization of a large number of load/stores without much growth in data and code segments. The average speedup for our optimization pass reaches roughly 13% if no profile information is available and 17% with profile information. The average code and data segment growth is controlled within 13%.
Reducing power while increasing performance with supercisc
Authors: Jones Alex K. , Hoare Raymond , Kusic Dara , Mehta Gayatri , Fazekas Josh , Foster John
Published: October 2006

Multiprocessor Systems on Chips (MPSoCs) have become a popular architectural technique to increase performance. However, MPSoCs may lead to undesirable power consumption characteristics for computing systems that have strict power budgets, such as PDAs, mobile phones, and notebook computers. This paper presents the super-complex instruction-set computing (SuperCISC) Embedded Processor Architecture and, in particular, investigates performance and power consumption of this device compared to traditional processor architecture-based execution. SuperCISC is a heterogeneous, multicore processor architecture designed to exceed performance of traditional embedded processors while maintaining a reduced power budget compared to low-power embedded processors. At the heart of the SuperCISC processor is a multicore VLIW (Very Large Instruction Word) containing several homogeneous execution cores/functional units. In addition, complex and heterogeneous combinational hardware function cores are tightly integrated to the core VLIW engine providing an opportunity for improved performance and reduced energy consumption. Our SuperCISC processor core has been synthesized for both a 90-nm Stratix II Field Programmable Gate Aray (FPGA) and a 160-nm standard cell Application-Specific Integrated Circuit (ASIC) fabrication process from OKI, each operating at approximately 167 MHz for the VLIW core. We examine several reasons for speedup and power improvement through the SuperCISC architecture, includingpredicated control flow,cycle compression, and a reduction in arithmetic power consumption, which we callpower compression. Finally, testing our SuperCISC processor with multimedia and signal-processing benchmarks, we show how the SuperCISC processor can provide performance improvements ranging from 7X to 160X with an average of 60X, whilealsoproviding orders of magnitude of power improvements for the computational kernels. The power improvements for our benchmark kernels range from just over 40X to over 400X, with an average savings exceeding 130X. By combining these power and performance improvements, our total energy improvements all exceed 1000X. As these savings are limited to the computational kernels of the applications, which often consume approximately 90% of the execution time, we expect our savings to approach the ideal application improvement of 10X.
Strategies for query unnesting in XML databases
Authors: May Norman , Helmer Sven , Moerkotte Guido
Published: October 2006

Queries formulated in a nested way are very common in XQuery. Unfortunately, their evaluation is usually very inefficient when done in a straightforward fashion. We present a framework for handling nested queries that is based on unnesting the queries after having translated them into an algebra. We not only present a collection of algebraic equivalences, but also supply a strategy on how to use them effectively. The full potential of the approach is demonstrated by applying our rewrites to actual queries and showing that performance gains of several orders of magnitude are possible.
XSKETCH synopses for XML data graphs
Authors: Polyzotis Neoklis , Garofalakis Minos
Published: October 2006

Effective support for XML query languages is becoming increasingly important with the emergence of new applications that access large volumes of XML data. All existing proposals for querying XML (e.g., XQuery) rely on a pattern-specification language that allows (1)
path navigation and branching through the label structure
of the XML data graph, and (2)
predicates on the values
of specific path/branch nodes, in order to reach the desired data elements. Clearly, optimizing such queries requires approximating the result cardinality of the referenced paths and hence hinges on the existence of concise synopsis structures that enable accurate compile-time selectivity estimates for complex path expressions over the base XML data. In this article, we introduce a novel approach to building and using statistical summaries of large XML data graphs for effective path-expression selectivity estimation. Our proposed graph-synopsis model (termed XSketch) exploits
localized graph stability
and
value-distribution summaries
(e.g., histograms) to accurately approximate (in limited space) the path and branching distribution, as well as the complex correlation patterns that can exist between and across path structure and element values in the data graph. To the best of our knowledge, ours is the first work to address this timely problem in the most general setting of graph-structured XML data with values, and complex (branching) path expressions.
An integrated efficient solution for computing frequent and top-
k
elements in data streams
Authors: Metwally Ahmed , Agrawal Divyakant , Abbadi Amr El
Published: October 2006

We propose an approximate integrated approach for solving both problems of finding the most popular
k
elements, and finding frequent elements in a data stream coming from a large domain. Our solution is space efficient and reports both frequent and top-
k
elements with tight guarantees on errors. For general data distributions, our top-
k
algorithm returns
k
elements that have roughly the highest frequencies; and it uses limited space for calculating frequent elements. For realistic Zipfian data, the space requirement of the proposed algorithm for solving the exact frequent elements problem decreases dramatically with the parameter of the distribution; and for top-
k
queries, the analysis ensures that only the top-
k
elements, in the correct order, are reported. The experiments, using real and synthetic data sets, show space reductions with hardly any loss in accuracy. Having proved the effectiveness of the proposed approach through both analysis and experiments, we extend it to be able to answer continuous queries about frequent and top-
k
elements. Although the problems of incremental reporting of frequent and top-
k
elements are useful in many applications, to the best of our knowledge, no solution has been proposed.
Perceptual limits on 2D motion-field visualization
Authors: Langer Michael S. , Pereira Javeen , Rekhi Dipinder
Published: October 2006

This paper examines perceptual issues in 2D motion-field visualization. Several aspects of motion-field perception are considered, including sensitivity to spatial gradients, number of motion layers, and motion blur. Our analysis concentrates on a specific popular method for 2D flow visualization, namely, line integral convolution (LIC). Using 2D spectral analysis, we examine a tradeoff that arises in dynamic LIC between the static motion blur cue, which indicates motion direction and the dynamic cue which indicates image speed. We also present a 2D spectral synthesis method for motion-field visualization, along with several examples. The synthesis method is simple to implement and to analyze in the frequency domain, which makes it a convenient tool for studying the perception of complex motion fields.
Exploring visual and automatic measures of perceptual fidelity in real and simulated imagery
Authors: McNamara Ann
Published: October 2006

This paper introduces a new psychophysical experiment developed to enable observers to judge the quality of computer graphics imagery with respect to the real scene it depicts. This new framework facilitates perceptual judgment of images against a real scene. Unlike previous work, which examined primitive objects under basic illumination, this experiment examines complex geometry illuminated using a calibrated light source. To ensure valid results, a commercial lighting booth containing rapid prototyped three-dimensional (3D) objects serves as the real scene. For comparison, a series of representative images, of varying quality, were rendered using the physically based Radiance lighting simulation software. Results from these experiments show that higher parameter settings, which lead to longer processing times, do not necessarily lead to higher quality images. To demonstrate that there is only modest benefit to setting parameters higher, images are subjected to further testing using two different visual quality discrimination operators; the Visual Differences Predictor (VDP) and the Structural SIMilarity (SSIM) for image-quality assessment. The results from the automatic operators correspond well with each other, in addition to yielding comparable outcomes as the psychophysical experiment. Although, a single scene was considered in the experiment, several scenes are tested using the image-quality metrics to lend further reliability to the assertion that higher parameter settings, which lead to extended processing times, do not necessarily lead to superior quality results.
A perceptual framework for contrast processing of high dynamic range images
Authors: Mantiuk Rafal , Myszkowski Karol , Seidel Hans-Peter
Published: October 2006

Image processing often involves an image transformation into a domain that is better correlated with visual perception, such as the wavelet domain, image pyramids, multiscale-contrast representations, contrast in retinex algorithms, and chroma, lightness, and colorfulness predictors in color-appearance models. Many of these transformations are not ideally suited for image processing that significantly modifies an image. For example, the modification of a single band in a multiscale model leads to an unrealistic image with severe halo artifacts. Inspired by gradient domain methods, we derive a framework that imposes constraints on the entire set of contrasts in an image for a full range of spatial frequencies. This way, even severe image modifications do not reverse the polarity of contrast. The strengths of the framework are demonstrated by aggressive contrast enhancement and a visually appealing tone mapping, which does not introduce artifacts. In addition, we perceptually linearize contrast magnitudes using a custom transducer function. The transducer function has been derived especially for the purpose of HDR images, based on the contrast-discrimination measurements for high-contrast stimuli.