bluuebunny/crossref_metadata_2025 huggingface dataset:
Declarative, formal, and extensible syntax definition for aspectJ
Authors: Bravenboer Martin , Tanter Éric , Visser Eelco
Published: January 2007

Aspect-Oriented Programming (AOP) is attracting attention from both research and industry, as illustrated by the ever-growing popularity of AspectJ, the
de facto
standard AOP extension of Java. From a compiler construction perspective AspectJ is interesting as it is a typical example of
compositional language, ie
a language composed of a number of separate languages with different syntactical styles: in addition to plain Java, AspectJ includes a language for defining pointcuts and one for defining advices. Language composition represents a non-trivial challenge for conventional parsing techniques. First, combining several languages with different lexical syntax leads to considerable complexity in the lexical states to processed. Second, as new language features for AOP are being explored, many research proposals are concerned with
further extending
the AspectJ language, resulting in a need for an extensible syntax definition.This paper shows how
scannerless parsing
elegantly addresses the issues encountered by conventional techniques when parsing AspectJ . We present the design of a modular, extensible, and formal definition of the lexical and context-free aspects of the AspectJ syntax in the Syntax Definition Formalism SDF, which is implemented by a scannerless, generalized-LR parser (SGLR). We introduce
grammar mixins
as a novel application of SDF's modularity features, which allows the declarative definition of different keyword policies and combination of extensions. We illustrate the modular extensibility of our definition with syntax extensions taken from current research on aspect languages. Finally, benchmarks show the reasonable performance of scannerless generalized-LR parsing for this grammar.
Method-specific dynamic compilation using logistic regression
Authors: Cavazos John , O'Boyle Michael F. P.
Published: January 2007

Determining the best set of optimizations to apply to a program has been a long standing problem for compiler writers. To reduce the complexity of this task, existing approaches typically apply the same set of optimizations to all procedures within a program, without regard to their particular structure. This paper develops a new method-specific approach that automatically selects the best optimizations on a per method basis within a dynamic compiler. Our approach uses the machine learning technique of logistic regression to automatically derive a predictive model that determines which optimizations to apply based on the features of a method. This technique is implemented in the Jikes RVM Java JIT compiler. Using this approach we reduce the average total execution time of the SPECjvm98 benchmarks by 29%. When the same heuristic is applied to the DaCapo+ benchmark suite, we obtain an average 33% reduction over the default level O2 setting.
A flexible framework for implementing software transactional memory
Authors: Herlihy Maurice , Luchangco Victor , Moir Mark
Published: January 2007

We describe DSTM2, a Java™ software library that provides a flexible framework for implementing object-based software transactional memory (STM). The library uses
transactional factories
to transform sequential (unsynchronized) classes into atomic (transactionally synchronized) ones, providing a substantial improvement over the awkward programming interface of our previous DSTM library. Furthermore, researchers can experiment with alternative STM mechanisms by providing their own factories. We demonstrate this flexibility by presenting two factories: one that uses essentially the same mechanisms as the original DSTM (with some enhancements),and another that uses a completely different approach.Because DSTM2 is packaged as a Java library, a wide range of programmers can easily try it out, and the community can begin to gain experience with transactional programming. Furthermore, researchers will be able to use the body of transactional programs that arises from this community experience to test and evaluate different STM mechanisms simply by supplying new transactional factories. We believe that this flexible approach will help to build consensus about the best ways to implement transactions, and will avoid the premature "lock-in" that may arise if STM mechanisms are baked into compilers before such experimentation is done.
Conscientious software
Authors: Gabriel Richard P. , Goldman Ron
Published: January 2007

Software needs to grow up and become responsible for itself and its own future by participating in its own installation and customization, maintaining its own health, and adapting itself to new circumstances, new users, and new uses. To create such software will require us to change some of our underlying assumptions about how we write programs. A promising approach seems to be to separate software that does the work (allopoietic)from software that keeps the system alive (autopoietic).
Enabling network-centric music performance in wide-area networks
Authors: Kurtisi Zefir , Gu Xiaoyuan , Wolf Lars
Published: January 2007

NMP on the Internet is not only possible, its delay bounds can satisfy the tight requirements involved in human perception while generating high-end audio quality for musicians and listeners alike.
Communication power optimization in a sensor network with a path-constrained mobile observer
Authors: Chakrabarti Arnab , Sabharwal Ashutosh , Aazhang Behnaam
Published: January 2007

We present a procedure for communication power optimization in a network of randomly distributed sensors with an observer (data collector) moving on a fixed path. The key challenge in using a mobile observer is that it remains within communication range of any sensor for a brief duration, and inability to transfer data in this duration leads to data loss. We establish that the process of data collection can be modeled by a queue with deadlines, where arrivals correspond to the observer entering the range of a sensor and a missed deadline means data loss. The queuing model is then used to identify the combination of system parameters that ensures adequate data collection with minimum power. The results obtained from the queuing analogy take a simple form in the asymptotic regime of dense sensor networks. Additionally, for sensor networks that cannot tolerate data loss, we derive a tight bound on minimum sensor separation that ensures that no data will be lost on account of mobility. We present two examples to illustrate our results, from which it is seen that power reduction by two orders of magnitude or more is typical relative to a static sensor network. The scenarios chosen for power comparisons also provide guidelines on the choice of path, if such a choice is available.
Stochastic coverage in heterogeneous sensor networks
Authors: Lazos Loukas , Poovendran Radha
Published: January 2007

We study the problem of
coverage
in planar heterogeneous sensor networks. Coverage is a performance metric that quantifies how well a field of interest is monitored by the sensor deployment. To derive analytical expressions of coverage for heterogeneous sensor networks, we formulate the coverage problem as a set intersection problem, a problem studied in integral geometry. Compared to previous analytical results, our formulation allows us to consider a network model where sensors are deployed according to an arbitrary stochastic distribution; sensing areas of sensors need not follow the unit disk model but can have any arbitrary shape; sensors need not have an identical sensing capability. Furthermore, our formulation does not assume deployment of sensors over an infinite plane and, hence, our derivations do not suffer from the border effect problem arising in a bounded field of interest. We compare our theoretical results with the spatial Poisson approximation that is widely used in modeling coverage. By computing the Kullback-Leibler and total variation distance between the probability density functions derived via our theoretical results, the Poisson approximation, and the simulation, we show that our formulas provide a more accurate representation of the coverage in sensor networks. Finally, we provide examples of calculating network parameters such as the network size and sensing range in order to achieve a desired degree of coverage.
Distributed metric calibration of ad hoc camera networks
Authors: Devarajan Dhanya , Radke Richard J. , Chung Haeyong
Published: January 2007

We discuss how to automatically obtain the metric calibration of an ad hoc network of cameras with no centralized processor. We model the set of uncalibrated cameras as nodes in a communication network, and propose a distributed algorithm in which each camera performs a local, robust bundle adjustment over the camera parameters and scene points of its neighbors in an overlay “vision graph.” We analyze the performance of the algorithm on both simulated and real data, and show that the distributed algorithm results in a fairer allocation of messages per node while achieving comparable calibration accuracy to centralized bundle adjustment.
Automated design flow for diode-based nanofabrics
Authors: Datta Kushal , Mukherjee Arindam , Ravindran Arun
Published: January 2007

We present an automated design flow for minimizing the use of diodes and switches (active devices) in design implementations on a nanofabric based on chemically self-assembled electronic nanotechnology as proposed in Goldstein and Budiu [2001]. Connectivity and logic in the nanofabric are realized using the switch and diode behaviors of molecular devices, unlike very large scale integrated (VLSI) circuits where complementary metal-oxide semiconductor (CMOS) gates are used. Similar to the optimization goal of reducing the number of gates in VLSI designs to minimize area, power dissipation, and delay, decreasing the number of switches and diodes used in the nanofabric can potentially minimize design implementation area and power dissipation, besides reducing the delay and signal drop between latched stages in order to improve performance. An integrated placement, topology selection, and routing approach for design implementation on the nanofabric is proposed. Note that this problem is fundamentally different from CMOS VLSI placement and routing because of the inherent routing-dependent logic realization in our target nanofabric. To the best of our knowledge this is the first reported work on automated integrated placement, topology selection, and routing for diode-based nanofabrics. A practical and scalable simulated annealing-based placement and routing algorithm has been implemented. On average, the integrated placement and routing approach achieves a reduction of 12% in the number of switches and diodes used for MCNC benchmarks, compared to separate placement and routing optimization results. The maximum reduction achieved in the number of active devices using our approach is 24%, and in general, we observed that the bigger the benchmark, the larger the improvement achieved.
Sample sizes for usability tests
Authors: Lewis James R.
Published: January 2007

"Really, how many users do you need to test? Three answers, all different."
---User Experience, Vol. 4, Issue 4, 2005
Storage performance virtualization via throughput and latency control
Authors: Zhang Jianyong , Sivasubramaniam Anand , Wang Qian , Riska Alma , Riedel Erik
Published: January 2007

I/O consolidation is a growing trend in production environments due to increasing complexity in tuning and managing storage systems. A consequence of this trend is the need to serve multiple users and/or workloads simultaneously. It is imperative to ensure that these users are insulated from each other by virtualization in order to meet any service-level objective (SLO). Previous proposals for performance virtualization suffer from one or more of the following drawbacks: (1) They rely on a fairly detailed performance model of the underlying storage system; (2) couple rate and latency allocation in a single scheduler, making them less flexible; or (3) may not always exploit the full bandwidth offered by the storage system.This article presents a two-level scheduling framework that can be built on top of an existing storage utility. This framework uses a low-level feedback-driven request scheduler, called AVATAR, that is intended to meet the latency bounds determined by the SLO. The load imposed on AVATAR is regulated by a high-level rate controller, called SARC, to insulate the users from each other. In addition, SARC is work-conserving and tries to fairly distribute any spare bandwidth in the storage system to the different users. This framework naturally decouples rate and latency allocation. Using extensive I/O traces and a detailed storage simulator, we demonstrate that this two-level framework can simultaneously meet the latency and throughput requirements imposed by an SLO, without requiring extensive knowledge of the underlying storage system.
Ultra low-cost defect protection for microprocessor pipelines
Authors: Shyam Smitha , Constantinides Kypros , Phadke Sujay , Bertacco Valeria , Austin Todd
Published: January 2007

The sustained push toward smaller and smaller technology sizes has reached a point where device reliability has moved to the forefront of concerns for next-generation designs. Silicon failure mechanisms, such as transistor wearout and manufacturing defects, are a growing challenge that threatens the yield and product lifetime of future systems. In this paper we introduce the
BulletProof
pipeline, the first ultra low-cost mechanism to protect a microprocessor pipeline and on-chip memory system from silicon defects. To achieve this goal we combine area-frugal on-line testing techniques and system-level checkpointing to provide the same guarantees of reliability found in traditional solutions, but at much lower cost. Our approach utilizes a microarchitectural checkpointing mechanism which creates coarse-grained epochs of execution, during which distributed on-line built in self-test (BIST) mechanisms validate the integrity of the underlying hardware. In case a failure is detected, we rely on the natural redundancy of instructionlevel parallel processors to repair the system so that it can still operate in a degraded performance mode. Using detailed circuit-level and architectural simulation, we find that our approach provides very high coverage of silicon defects (89%) with little area cost (5.8%). In addition, when a defect occurs, the subsequent degraded mode of operation was found to have only moderate performance impacts, (from 4% to 18% slowdown).
Instruction scheduling for a tiled dataflow architecture
Authors: Mercaldi Martha , Swanson Steven , Petersen Andrew , Putnam Andrew , Schwerin Andrew , Oskin Mark , Eggers Susan J.
Published: January 2007

This paper explores hierarchical instruction scheduling for a tiled processor. Our results show that at the top level of the hierarchy, a simple profile-driven algorithm effectively minimizes operand latency. After this schedule has been partitioned into large sections, the bottom-level algorithm must more carefully analyze program structure when producing the final schedule.Our analysis reveals that at this bottom level, good scheduling depends upon carefully balancing instruction contention for processing elements and operand latency between producer and consumer instructions. We develop a parameterizable instruction scheduler that more effectively optimizes this trade-off. We use this scheduler to determine the contention-latency sweet spot that generates the best instruction schedule for each application. To avoid this application-specific tuning, we also determine the parameters that produce the best performance across all applications. The result is a contention-latency setting that generates instruction schedules for all applications in our workload that come within 17% of the best schedule for each.
HeapMD
Authors: Chilimbi Trishul M. , Ganapathy Vinod
Published: January 2007

We present the design, implementation, and evaluation of HeapMD, a dynamic analysis tool that finds heap-based bugs using anomaly detection. HeapMD is based upon the observation that, in spite of the evolving nature of the heap, several of its properties remain stable. HeapMD uses this observation in a novel way: periodically, during the execution of the program, it computes a suite of metrics which are sensitive to the state of the heap. These metrics track heap behavior, and the stability of the heap reflects quantitatively in the values of these metrics. The "normal" ranges of stable metrics, obtained by running a program on multiple inputs, are then treated as indicators of correct behaviour, and are used in conjunction with an anomaly detector to find heap-based bugs. Using HeapMD, we were able to find 40 heap-based bugs, 31 of them previously unknown, in 5 large, commercial applications.
A program transformation and architecture support for quantum uncomputation
Authors: Schuchman Ethan , Vijaykumar T. N.
Published: January 2007

Quantum computing's power comes from new algorithms that exploit quantum mechanical phenomena for computation. Quantum algorithms are different from their classical counterparts in that quantum algorithms rely on algorithmic structures that are simply not present in classical computing. Just as classical program transformations and architectures have been designed for common classical algorithm structures, quantum program transformations and quantum architectures should be designed with quantum algorithms in mind. Because quantum algorithms come with these new algorithmic structures, resultant quantum program transformations and architectures may look very different from their classical counterparts.This paper focuses on uncomputation, a critical and prevalent structure in quantum algorithms, and considers how program transformations, and architecture support should be designed to accommodate uncomputation. In this paper,we show a simple quantum program transformation that exposes independence between uncomputation and later computation. We then propose a multicore architecture tailored to this exposed parallelism and propose a scheduling policy that efficiently maps such parallelism to the multicore architecture. Our policy achieves parallelism between uncomputation and later computation while reducing cumulative communication distance. Our scheduling and architecture allows significant speedup of quantum programs (between 1.8x and 2.8x speedup in Shor's factoring algorithm), while reducing cumulative communication distance 26%.
Computation spreading
Authors: Chakraborty Koushik , Wells Philip M. , Sohi Gurindar S.
Published: January 2007

In canonical parallel processing, the operating system (OS) assigns a processing core to a single thread from a multithreaded server application. Since different threads from the same application often carry out similar computation, albeit at different times, we observe extensive code reuse among different processors, causing redundancy (e.g., in our server workloads, 45-65% of all instruction blocks are accessed by all processors). Moreover, largely independent fragments of computation compete for the same private resources causing destructive interference. Together, this redundancy and interference lead to poor utilization of private microarchitecture resources such as caches and branch predictors.We present
Computation Spreading
(CSP), which employs hardware migration to distribute a thread's dissimilar fragments of computation across the multiple processing cores of a chip multiprocessor (CMP), while grouping similar computation fragments from different threads together. This paper focuses on a specific example of CSP for OS intensive server applications: separating application level (user) computation from the OS calls it makes.When performing CSP, each core becomes temporally specialized to execute certain computation fragments, and the same core is repeatedly used for such fragments. We examine two specific thread assignment policies for CSP, and show that these policies, across four server workloads, are able to reduce instruction misses in private L2 caches by 27-58%, private L2 load misses by 0-19%, and branch mispredictions by 9-25%.
Tartan
Authors: Mishra Mahim , Callahan Timothy J. , Chelcea Tiberiu , Venkataramani Girish , Goldstein Seth C. , Budiu Mihai
Published: January 2007

Spatial Computing (SC) has been shown to be an energy-efficient model for implementing program kernels. In this paper we explore the feasibility of using SC for more than small kernels. To this end, we evaluate the performance and energy efficiency of entire applications on Tartan, a general-purpose architecture which integrates a reconfigurable fabric (RF) with a superscalar core. Our compiler automatically partitions and compiles an application into an instruction stream for the core and a configuration for the RF. We use a detailed simulator to capture both timing and energy numbers for all parts of the system.Our results indicate that a hierarchical RF architecture, designed around a scalable interconnect, is instrumental in harnessing the benefits of spatial computation. The interconnect uses static configuration and routing at the lower levels and a packet-switched, dynamically-routed network at the top level. Tartan is most energyefficient when almost all of the application is mapped to the RF, indicating the need for the RF to support most general-purpose programming constructs. Our initial investigation reveals that such a system can provide, on average, an order of magnitude improvement in energy-delay compared to an aggressive superscalar core on single-threaded workloads.
Efficiently exploring architectural design spaces via predictive modeling
Authors: Ïpek Engin , McKee Sally A. , Caruana Rich , de Supinski Bronis R. , Schulz Martin
Published: January 2007

Architects use cycle-by-cycle simulation to evaluate design choices and understand tradeoffs and interactions among design parameters. Efficiently exploring exponential-size design spaces with many interacting parameters remains an open problem: the sheer number of experiments renders detailed simulation intractable. We attack this problem via an automated approach that builds accurate, confident predictive design-space models. We simulate sampled points, using the results to teach our models the function describing relationships among design parameters. The models produce highly accurate performance estimates for other points in the space, can be queried to predict performance impacts of architectural changes, and are very fast compared to simulation, enabling efficient discovery of tradeoffs among parameters in different regions. We validate our approach via sensitivity studies on memory hierarchy and CPU design spaces: our models generally predict IPC with only 1-2% error and reduce required simulation by two orders of magnitude. We also show the efficacy of our technique for exploring chip multiprocessor (CMP) design spaces: when trained on a 1% sample drawn from a CMP design space with 250K points and up to 55x performance swings among different system configurations, our models predict performance with only 4-5% error on average. Our approach combines with techniques to reduce time per simulation, achieving net time savings of three-four orders of magnitude.
Introspective 3D chips
Authors: Mysore Shashidhar , Agrawal Banit , Srivastava Navin , Lin Sheng-Chih , Banerjee Kaustav , Sherwood Tim
Published: January 2007

While the number of transistors on a chip increases exponentially over time, the productivity that can be realized from these systems has not kept pace. To deal with the complexity of modern systems, software developers are increasingly dependent on specialized development tools such as security profilers, memory leak identifiers, data flight recorders, and dynamic type analysis. Many of these tools require full-system data which covers multiple interacting threads, processes, and processors. Reducing the performance penalty and complexity of these software tools is critical to those developing next generation applications, and many researchers have proposed adding specialized hardware to assist in profiling and introspection. Unfortunately, while this additional hardware would be incredibly beneficial to developers, the cost of this hardware must be paid on every single die that is manufactured.In this paper, we argue that a new way to attack this problem is with the addition of specialized analysis hardware built on separate active layers stacked vertically on the processor die using 3D IC technology. This provides a modular "snap-on" functionality that could be included with developer systems, and omitted from consumer systems to keep the cost impact to a minimum. In this paper we describe the advantage of using inter-die vias for introspection and we quantify the impact they can have in terms of the area, power, temperature, and routability of the resulting systems. We show that hardware stubs could be inserted into commodity processors at design time that would allow analysis layers to be bonded to development chips, and that these stubs would increase area and power by no more than 0.021mm
2
and 0.9% respectively.
A performance counter architecture for computing accurate CPI components
Authors: Eyerman Stijn , Eeckhout Lieven , Karkhanis Tejas , Smith James E.
Published: January 2007

A common way of representing processor performance is to use Cycles per Instruction (CPI) `stacks' which break performance into a baseline CPI plus a number of individual miss event CPI components. CPI stacks can be very helpful in gaining insight into the behavior of an application on a given microprocessor; consequently, they are widely used by software application developers and computer architects. However, computing CPI stacks on superscalar out-of-order processors is challenging because of various overlaps among execution and miss events (cache misses, TLB misses, and branch mispredictions).This paper shows that meaningful and accurate CPI stacks can be computed for superscalar out-of-order processors. Using interval analysis, a novel method for analyzing out-of-order processor performance, we gain understanding into the performance impact of the various miss events. Based on this understanding, we propose a novel way of architecting hardware performance counters for building accurate CPI stacks. The additional hardware for implementing these counters is limited and comparable to existing hardware performance counter architectures while being significantly more accurate than previous approaches.
Accurate and efficient regression modeling for microarchitectural performance and power prediction
Authors: Lee Benjamin C. , Brooks David M.
Published: January 2007

We propose regression modeling as an efficient approach for accurately predicting performance and power for various applications executing on any microprocessor configuration in a large microarchitectural design space. This paper addresses fundamental challenges in microarchitectural simulation cost by reducing the number of required simulations and using simulated results more effectively via statistical modeling and inference.Specifically, we derive and validate regression models for performance and power. Such models enable computationally efficient statistical inference, requiring the simulation of only 1 in 5 million points of a joint microarchitecture-application design space while achieving median error rates as low as 4.1 percent for performance and 4.3 percent for power. Although both models achieve similar accuracy, the sources of accuracy are strikingly different. We present optimizations for a baseline regression model to obtain (1) application-specific models to maximize accuracy in performance prediction and (2) regional power models leveraging only the most relevant samples from the microarchitectural design space to maximize accuracy in power prediction. Assessing sensitivity to the number of samples simulated for model formulation, we find fewer than 4,000 samples from a design space of approximately 22 billion points are sufficient. Collectively, our results suggest significant potential in accurate and efficient statistical inference for microarchitectural design space exploration via regression models.
Stealth prefetching
Authors: Cantin Jason F. , Lipasti Mikko H. , Smith James E.
Published: January 2007

Prefetching in shared-memory multiprocessor systems is an increasingly difficult problem. As system designs grow to incorporate larger numbers of faster processors, memory latency and interconnect traffic increase. While aggressive prefetching techniques can mitigate the increasing memory latency, they can harm performance by wasting precious interconnect bandwidth and prematurely accessing shared data, causing state downgrades at remote nodes that force later upgrades.This paper investigates Stealth Prefetching, a new technique that utilizes information from Coarse-Grain Coherence Tracking (CGCT) for prefetching data aggressively, stealthily, and efficiently in a broadcast-based shared-memory multiprocessor system. Stealth Prefetching utilizes CGCT to identify regions of memory that are not shared by other processors, aggressively fetches these lines from DRAM in open-page mode, and moves them close to the processor in anticipation of future references. Our analysis with commercial, scientific, and multiprogrammed workloads show that Stealth Prefetching provides an average speedup of 20% over an aggressive baseline system with conventional prefetching.
Automatic generation of peephole superoptimizers
Authors: Bansal Sorav , Aiken Alex
Published: January 2007

Peephole optimizers are typically constructed using human-written pattern matching rules, an approach that requires expertise and time, as well as being less than systematic at exploiting all opportunities for optimization. We explore fully automatic construction of peephole optimizers using brute force superoptimization. While the optimizations discovered by our automatic system may be less general than human-written counterparts, our approach has the potential to automatically learn a database of thousands to millions of optimizations, in contrast to the hundreds found in current peephole optimizers. We show experimentally that our optimizer is able to exploit performance opportunities not found by existing compilers; in particular, we show speedups from 1.7 to a factor of 10 on some compute intensive kernels over a conventional optimizing compiler.
Propositional Satisfiability and Constraint Programming
Authors: Bordeaux Lucas , Hamadi Youssef , Zhang Lintao
Published: January 2007

Propositional Satisfiability (SAT) and Constraint Programming (CP) have developed as two relatively independent threads of research cross-fertilizing occasionally. These two approaches to problem solving have a lot in common as evidenced by similar ideas underlying the branch and prune algorithms that are most successful at solving both kinds of problems. They also exhibit differences in the way they are used to state and solve problems since SAT's approach is, in general, a black-box approach, while CP aims at being tunable and programmable. This survey overviews the two areas in a comparative way, emphasizing the similarities and differences between the two and the points where we feel that one technology can benefit from ideas or experience acquired from the other.
IMMERSCOM 2007
Authors: Lee Newton
Published: January 2007

IMMERSCOM is the first international conference that focuses on bridging the traditional gap between immersive technologies and networking for the capturing, processing, analyzing, transmitting and enabling the remote fruition of objects, environments, and bio-entities.
A practical revocation scheme for broadcast encryption using smartcards
Authors: Kogan Noam , Shavitt Yuval , Wool Avishai
Published: January 2007

We present an anti-pirate revocation scheme for broadcast encryption systems (e.g., pay TV), in which the data is encrypted to ensure payment by users. In the systems we consider, decryption of keys is done on smartcards and key management is done in-band. Our starting point is a scheme of Naor and Pinkas. Their basic scheme uses secret sharing to remove up to
t
parties, is information-theoretic secure against coalitions of size
t
, and is capable of creating a new group key. However, with current smartcard technology, this scheme is only feasible for small system parameters, allowing up to about 100 pirates to be revoked before all the smartcards need to be replaced. We first present a novel implementation method of their basic scheme that distributes the work among the smartcard, set-top terminal, and center. Based on this, we construct several improved schemes for many revocation rounds that scale to realistic system sizes. We allow up to about 10,000 pirates to be revoked using current smartcard technology before recarding is needed. The transmission lengths of our constructions are on par with those of the best tree-based schemes. However, our constructions have much lower smartcard CPU complexity: only
O
(1) smartcard operations per revocation round (a single 10-byte field multiplication and addition), as opposed to the complexity of the best tree-based schemes, which is polylogarithmic in the number of users. We evaluate the system behavior via an exhaustive simulation study coupled with a queueing theory analysis. Our simulations show that with mild assumptions on the piracy discovery rate, our constructions can perform effective pirate revocation for realistic broadcast encryption scenarios.
A Conversation with Douglas W. Jones and Peter G. Neumann
Authors: O'Hanlon Charlene
Published: January 2007

Elections form the fundamental basis of all democracies. In light of many past problems with the integrity of election processes around the world, ongoing efforts have sought to increase the use of computers and communications in elections to help automate the process. Unfortunately, many existing computer-related processes are poorly conceived and implemented, introducing new problems related to such issues as voter confidentiality and privacy, computer system integrity, accountability and resolution of irregularities, ease of administration by election officials, and ease of use by voters—with many special problems for those with various handicaps. Overall, the issues relating to computer security provide a representative cross-section of the difficulties inherent in attempting to develop and operate trustworthy systems for other applications. These issues, of course, have relevance internationally and are increasingly timely.
Review of "Spring in Action by Craig Walls and Ryan Breidenbach," Manning Publications, 2005, $44.95, ISBN: 1932394354.
Authors: Wolf Markus
Published: January 2007

Review of "Spring in Action by Craig Walls and Ryan Breidenbach," Manning Publications, 2005, $44.95, ISBN: 1932394354.
E2K
Authors: Llorá Xavier
Published: January 2007

Simulink [8] has become a reference framework to accurately design, simulate, implement, and test control, signal processing, communications, and other time-varying systems. A key element of its success is a simple visual programming approach. It allows users to create targeted designs by reusing basic building-block functionalities and graphically creating a flow of execution among them. Users just need to focus on the target problem, not being disturbed by implementation details. Few attempts have been conducted in the evolutionary computation community to provide such a framework that allows beginners and researchers to share a common ground that allow them to deploy and quickly reuse the basic components of evolutionary algorithms. Evolvica [1] was a first effort to push toward this endeavor. Developed at Technical University of Ilmenau, it provided a first attempt to create a visual programming oriented framework. The last Evolvica release dates back to July 2004. Other tools such as ECJ [7] and Open BEAGLE [2] have been more oriented to cover researchers' needs than to create such an integration framework.
What can context do for web services?
Authors: Maamar Zakaria , Benslimane Djamal , Narendra Nanjangud C.
Published: January 2007

Context-aware Web service would significantly benefit the interactions between human, applications, and the environment.
The challenges of broadening the scope of software product families
Authors: Bosch Jan
Published: January 2007

Addressing the challenges involved in broadening the scope of software product families.
Extensional equivalence and singleton types
Authors: Stone Christopher A. , Harper Robert
Published: January 2007

We study the λ

ΠΣ
S

≤
calculus, which contains singleton types
S
(
M
) classifying terms of base type provably equivalent to the term
M
. The system includes dependent types for pairs and functions (Σ and Π) and a subtyping relation induced by regarding singletons as subtypes of the base type. The decidability of type checking for this language is non-obvious, since to type check we must be able to determine equivalence of well-formed terms. But in the presence of singleton types, the provability of an equivalence judgment Γ ⊢
M
1
≡
M
2
:
A
can depend both on the typing context Γ and on the particular type
A
at which
M
1
and
M
2
are compared.We show how to prove decidability of term equivalence, hence of type checking, in λ

ΠΣ
S

≤
by exhibiting a type-directed algorithm for directly computing normal forms. The correctness of normalization is shown using an unusual variant of Kripke logical relations organized around sets; rather than defining a logical equivalence relation, we work directly with (subsets of) the corresponding equivalence classes.We then provide a more efficient algorithm for checking type equivalence without constructing normal forms. We also show that type checking, subtyping, and all other judgments of the system are decidable.The λ

ΠΣ
S

≤
calculus models type constructors and kinds in the intermediate language used by the TILT compiler for Standard ML to implement the SML module system. The decidability of λ

ΠΣ
S

≤
term equivalence allows us to show decidability of type checking for TILT's intermediate language. We also obtain a consistency result that allows us to prove type safety for the intermediate language. The algorithms derived here form the core of the type checker used for internal type checking in TILT.
The strength of replacement in weak arithmetic
Authors: Cook Stephen , Thapen Neil
Published: January 2007

Thereplacement(orcollectionorchoice) axiom scheme BB(Γ) asserts bounded quantifier exchange as follows: ∀i< |a| ∃x<aϕ(i,x) → ∃w∀i< |a|ϕ(i,[w]i), for ϕ in the class Γ of formulas. The theoryS12proves the scheme BB(Σb1), and thus inS12every Σb1formula is equivalent to a strict Σb1formula (in which all non-sharply-bounded quantifiers are in front). Here we prove (sometimes subject to an assumption) that certain theories weaker thanS12do not prove either BB(Σb1) or BB(Σb0). We show (unconditionally) thatV0does not prove BB(Σb0), where V0(essentially IΣ1,b0) is the two-sorted theory associated with the complexity class AC0. We show that PV does not prove BB(Σb0), assuming that integer factoring is not possible in probabilistic polynomial time. Johannsen and Pollett introduced the theoryC02associated with the complexity class TC0, and later introduced an apparently weaker theory Δb1− CR for the same class. We use our methods to show that Δb1− CR is indeed weaker thanC02, assuming that RSA is secure against probabilistic polynomial time attack.Our main tool is the KPT witnessing theorem.
Splitting an operator
Authors: Vennekens Joost , Gilis David , Denecker Marc
Published: January 2007

It is well known that, under certain conditions, it is possible to
split
logic programs under stable model semantics, that is, to divide such a program into a number of different “levels”, such that the models of the entire program can be constructed by incrementally constructing models for each level. Similar results exist for other nonmonotonic formalisms, such as auto-epistemic logic and default logic. In this work, we present a general, algebraic splitting theory for logics with a fixpoint semantics. Together with the framework of
approximation theory
, a general fixpoint theory for arbitrary operators, this gives us a uniform and powerful way of deriving splitting results for each logic with a fixpoint semantics. We demonstrate the usefulness of these results, by generalizing existing results for logic programming, auto-epistemic logic and default logic.
Computing contour generators of evolving implicit surfaces
Authors: Plantinga Simon , Vegter Gert
Published: January 2007

The contour generator is an important visibility feature of a smooth object seen under parallel projection. It is the curve on the surface which seperates front-facing from back-facing regions. The apparent contour is the projection of the contour generator onto a plane perpendicular to the view direction. Both curves play an important role in computer graphics.Our goal is to obtain fast and robust algorithms that compute the contour generator with a guarantee of topological correctness. To this end, we first study the singularities of the contour generator and apparent contour for both generic views and generic time-dependent projections, for example, when the surface is rotated or deformed. The singularities indicate when components of the contour generator merge or split as time evolves.We present an algorithm to compute an initial contour generator by using a dynamic step size. An interval test guarantees the topological correctness. This initial contour generator can thus be maintained under a time-dependent projection by examining its singularities.
Parametrizations for triangular
G

k

spline surfaces of low degree
Authors: Prautzsch Hartmut , Umlauf Georg
Published: January 2007

In this article, we present regularly parametrized
G

k

free-form spline surfaces that extend box and half-box splines over regular triangular grids. The polynomial degree of these splines is max{4
k
+ 1, ⌈3k/2 + 1⌉r}, where
r
∈ ℕ can be chosen arbitrarily and determines the flexibility at extraordinary points. The
G

k

splines presented in this article depend crucially on low-degree (re-)parametrizations of piecewise polynomial hole fillings. The explicit construction of such parametrizations forms the core of this work and we present two classes of singular and regular parametrizations. Also, we show how to build box and half-box spline surfaces of arbitrarily high smoothness with holes bounded by only
n
patches, in principle.
Searching for experts on the Web
Authors: Becerra-Fernandez Irma
Published: January 2007

This article presents the role of ontologies and Web mining techniques in the construction and maintenance of experts' profiles. This article also discusses the development of contemporary expertise-locator knowledge management systems and, specifically, the implementation details of two such systems: the Searchable Answer Generating Engine (SAGE), and Expert Seeker. SAGE is a Web-based expertise locator system, which searches for researchers in universities in Florida based on specified criteria, including expertise in a specific domain. Expert Seeker's purpose is to search for experts in one of the best-known knowledge organizations, the National Aeronautics and Space Administration. Implementation details, results to date, and future plans for these systems are also presented.
Finding a maximum likelihood tree is hard
Authors: Chor Benny , Tuller Tamir
Published: January 2007

Maximum likelihood (ML) is an increasingly popular optimality criterion for selecting evolutionary trees [Felsenstein 1981]. Finding optimal ML trees appears to be a very hard computational task, but for tractable cases, ML is the method of choice. In particular, algorithms and heuristics for ML take longer to run than algorithms and heuristics for the second major character based criterion, maximum parsimony (MP). However, while MP has been known to be NP-complete for over 20 years [Foulds and Graham, 1982; Day et al. 1986], such a hardness result for ML has so far eluded researchers in the field.An important work by Tuffley and Steel [1997] proves quantitative relations between the parsimony values of given sequences and the corresponding log likelihood values. However, a direct application of their work would only give an
exponential time
reduction from MP to ML. Another step in this direction has recently been made by Addario-Berry et al. [2004], who proved that
ancestral maximum likelihood
(AML) is NP-complete. AML “lies in between” the two problems, having some properties of MP and some properties of ML. Still, the AML proof is not directly applicable to the ML problem.We resolve the question, showing that “regular” ML on phylogenetic trees is indeed intractable. Our reduction follows the vertex cover reductions for MP [Day et al. 1986] and AML [Addario-Berry et al. 2004], but its starting point is an approximation version of vertex cover, known as gap vc. The crux of our work is not the reduction, but its correctness proof. The proof goes through a series of tree modifications, while controlling the likelihood losses at each step, using the bounds of Tuffley and Steel [1997]. The proof can be viewed as correlating the value of any ML solution to an arbitrarily close approximation to vertex cover.
Developing safety critical software for an unmanned aerial vehicle situational awareness tool
Authors: Sward Ricky E. , Gerken Mark
Published: January 2007

In this paper, we describe our application of the SPARK programming language to the development of flight control software for an Unmanned Aerial Vehicle (UAV). The SPARK language was used during a senior-level software engineering course at the US Air Force Academy. This paper uses the year-long project from this course as an example application of SPARK. The process we used to build an interface between C++ and Ada is discussed along with our experiences with using SPARK.
When to migrate legacy embedded applications
Authors: Mosley David
Published: January 2007

This experience report will focus on the issues which drive developers to migrate their application development to a new host or new target or new tool set. If there is no reason to change the embedded application, then there will obviously be no migration. Often there are compelling reasons to change the application, in which case the benefits of change will have to out weigh the costs. If the change can be incorporated using the existing tools, host, and target, then so much the better. But, if the existing tools, host, and/or target are no longer viable, then the cost of making a change to the application must include the cost of a migration.
Preparing heterogeneous XML for full-text search
Authors: Lehtonen Miro
Published: January 2007

XML retrieval is facing new challenges when applied to heterogeneous XML documents, where next to nothing about the document structure can be taken for granted. We have developed solutions where some of the heterogeneity issues are addressed. Our fragment selection algorithm selectively divides a heterogeneous document collection into equi-sized fragments with full-text content. If the content is considered too data-oriented, it is not accepted. The algorithm needs no information about element names. In addition, three techniques for fragment expansion are presented, all of which yield a 13--17% average improvement in average precision. These techniques and algorithms are among the first steps in developing document-type-independent indexing methods for the full text in heterogeneous XML collections.
Multipattern string matching with
q
-grams
Authors: Salmela Leena , Tarhio Jorma , Kytöjoki Jari
Published: January 2007

We present three algorithms for exact string matching of multiple patterns. Our algorithms are filtering methods, which apply
q
-grams and bit parallelism. We ran extensive experiments with them and compared them with various versions of earlier algorithms, e.g., different trie implementations of the Aho--Corasick algorithm. All of our algorithms appeared to be substantially faster than earlier solutions for sets of 1,000--10,000 patterns and the good performance of two of them continues to 100,000 patterns. The gain is because of the improved filtering efficiency caused by
q
-grams.