bluuebunny/crossref_metadata_2025 huggingface dataset:
DRAMsim
Authors: Wang David , Ganesh Brinda , Tuaycharoen Nuengwong , Baynes Kathleen , Jaleel Aamer , Jacob Bruce
Published: February 2006

As memory accesses become slower with respect to the processor and consume more power with increasing memory size, the focus of memory performance and power consumption has become increasingly important. With the trend to develop multi-threaded, multi-core processors, the demands on the memory system will continue to scale. However, determining the optimal memory system configuration is non-trivial. The memory system performance is sensitive to a large number of parameters. Each of these parameters take on a number of values and interact in fashions that make overall trends difficult to discern. A comparison of the memory system architectures becomes even harder when we add the dimensions of power consumption and manufacturing cost. Unfortunately, there is a lack of tools in the public-domain that support such studies. Therefore, we introduce DRAMsim, a detailed and highly-configurable C-based memory system simulator to fill this gap. DRAMsim implements detailed timing models for a variety of existing memories, including SDRAM, DDR, DDR2, DRDRAM and FB-DIMM, with the capability to easily vary their parameters. It also models the power consumption of SDRAM and its derivatives. It can be used as a standalone simulator or as part of a more comprehensive system-level model. We have successfully integrated DRAMsim into a variety of simulators including MASE [15], Sim-alpha [14], BOCHS[2] and GEMS[13]. The simulator can be downloaded from www.ece.umd.edu/dramsim.
Improving memory system performance with energy-efficient value speculation
Authors: Sam Nana B. , Burtscher Martin
Published: February 2006

Microprocessor speeds have been improving much faster than memory speeds, resulting in the CPU spending a larger and larger amount of time waiting for data. Processor designers have employed several ways to improve memory performance, including hierarchical caching, prefetching, and faster memory chips. Yet, memory accesses still represent a major performance bottleneck and much remains to be done to tolerate the increasing memory latencies. Load-value prediction has been shown to effectively hide some of this latency. However, the hardware required to achieve good performance is substantial, making load-value prediction unappealing in light of increasing power constraints. In this paper, we present a novel predictor that significantly increases CPU performance while at the same time decreasing the energy consumption of the entire processor relative to a baseline with a well-performing hybrid load-value predictor.
MyLifeBits
Authors: Gemmell Jim , Bell Gordon , Lueder Roger
Published: February 2006

Developing a platform for recording, storing, and accessing a personal lifetime archive.
Four dynamics for bringing use back into software reuse
Authors: Desouza Kevin C. , Awazu Yukika , Tiwana Amrit
Published: February 2006

Reuse is such a powerful tool---so why isn't it more popular?
Insight and perspectives for content delivery networks
Authors: Pallis George , Vakali Athena
Published: February 2006

Striking a balance between the costs for Web content providers and the quality of service for Web customers.
Seven key interventions for data warehouse success
Authors: Chenoweth Tim , Corral Karen , Demirkan Haluk
Published: February 2006

The success of data warehouses depends on the interaction of technology and social context. We present new insights into the implementation process and interventions that can lead to success.
Budgeting process for information security expenditures
Authors: Gordon Lawrence A. , Loeb Martin P.
Published: February 2006

Empirical evidence shows that cost-benefit analysis is a sound basis for budgeting information security expenditures.
Counting boulders and measuring mountains
Authors: Armour Phillip G.
Published: February 2006

Accuracy and the measurement of peaks and projects.
New Directions for
CACM
?
Authors: Patterson David A.
Published: February 2006

Much has changed since the 1980s when the current format of
Communications of the ACM
was cast. What should be the mission of ACM's flagship publication in the 21st century?
How to think about security failures
Authors: Campbell Scott
Published: February 2006

Understanding complexity and feedback in security models highlights the need for better failure modes in solutions.
Digital memories in an era of ubiquitous computing and abundant storage
Authors: Czerwinski Mary , Gage Douglas W. , Gemmell Jim , Marshall Catherine C. , Pérez-Quiñones Manuel A. , Skeels Meredith M. , Catarci Tiziana
Published: February 2006

A lifetime of digital memories is possible but raises many social, as well as technological, questions.
Usable privacy and security for personal information management
Authors: Karat Clare-Marie , Brodie Carolyn , Karat John
Published: February 2006

The goal is a policy workbench enabling users to create and transform natural language policies into machine-readable code for enforcement and compliance audits.
Searching to eliminate personal information management
Authors: Cutrell Edward , Dumais Susan T. , Teevan Jaime
Published: February 2006

Search systems can alleviate the need to organize personal information by helping us find it no matter where we encountered it, what we remember about it, and even if we forget it exists.
Data unification in personal information management
Authors: Karger David R. , Jones William
Published: February 2006

Users need ways to unify, simplify, and consolidate information too often fragmented by location, device, and software application.
Evaluating personal information management behaviors and tools
Authors: Kelly Diane
Published: February 2006

How to study and understand the idiosyncratic PIM behaviors we exhibit naturally at home, at work, and in between, in the interests of developing future PIM tools.
Information source selection for resource constrained environments
Authors: Aksoy Demet
Published: February 2006

Distributed information retrieval has pressing scalability concerns due to the growing number of independent sources of on-line data and the emerging applications. A promising solution to distributed retrieval is metasearching, which dispatches a user's query to multiple sources and gathers the results into a single result set. An important component of metasearching is selecting the set of information sources most likely to provide relevant documents. Recent research has focused on how to obtain statistics for the selection task. In this paper we discuss different information source selection approaches and their applicability for resource-constrained sensor network applications.
LiXQuery
Authors: Hidders Jan , Michiels Philippe , Paredaens Jan , Vercammen Roel
Published: February 2006

XQuery is considered to become the standard query language for XML documents. However, the complete XQuery syntax and semantics seem too complicated for research and educational purposes. By defining a concise backwards compatible subset of XQuery with a complete formal description, we provide a practical foundation for XQuery research. We pay special attention to usability by supporting the most typical XQuery expressions.
From databases to dataspaces
Authors: Franklin Michael , Halevy Alon , Maier David
Published: February 2006

The development of relational database management systems served to focus the data management community for decades, with spectacular results. In recent years, however, the rapidly-expanding demands of "data everywhere" have led to a field comprised of interesting and productive efforts, but without a central focus or coordinated agenda. The most acute information management challenges today stem from organizations (e.g., enterprises, government agencies, libraries, "smart" homes) relying on a large number of diverse, interrelated data sources, but having no way to manage their
dataspaces
in a convenient, integrated, or principled fashion. This paper proposes dataspaces and their support systems as a new agenda for data management. This agenda encompasses much of the work going on in data management today, while posing additional research objectives.
Scientific data management in the coming decade
Authors: Gray Jim , Liu David T. , Nieto-Santisteban Maria , Szalay Alex , DeWitt David J. , Heber Gerd
Published: February 2006

Scientific instruments and computer simulations are creating vast data stores that require new scientific methods to analyze and organize the data. Data volumes are approximately doubling each year. Since these new instruments have extraordinary precision, the data quality is also rapidly improving. Analyzing this data to find the subtle effects missed by previous studies requires algorithms that can simultaneously deal with huge datasets and that can find very subtle effects --- finding both needles in the haystack and finding very small haystacks that were undetected in previous measurements.
An apples-to-apples comparison of two database journals
Authors: Bernstein Philip A. , Bertino Elisa , Heuer Andreas , Jensen Christian S. , Meyer Holger , Özsu M. Tamer , Snodgrass Richard T. , Whang Kyu-Young
Published: February 2006

This paper defines a collection of metrics on manuscript reviewing and presents historical data for
ACM Transactions on Database Systems
and
The VLDB Journal.
Report on the DB/IR panel at SIGMOD 2005
Authors: Amer-Yahia Sihem , Case Pat , Rölleke Thomas , Shanmugasundaram Jayavel , Weikum Gerhard
Published: February 2006

This paper summarizes the salient aspects of the SIGMOD 2005 panel on "Databases and Information Retrieval: Rethinking the Great Divide". The goal of the panel was to discuss whether we should rethink data management systems architectures to truly merge Database (DB) and Information Retrieval (IR) technologies. The panel had very high attendance and generated lively discussions.
Report on the first IEEE international workshop on networking meets databases (NetDB'05)
Authors: Shahabi Cyrus , Govindan Ramesh , Aberer Karl
Published: February 2006

In this report, to the best of our ability, we try to summarize the presentations and discussions occurred within the First IEEE International Workshop on Networking Meets Databases (NetDB) which was held in Tokyo Japan on April 8th and 9th, 2005. NetDB was one of the many (11 to be exact) satellite workshops of the IEEE ICDE (International Conference on Data Engineering) 2005 conference. This workshop is part of the very few initiatives in bringing the networking and database communities together. The focus research areas of NetDB 2005 were sensor and peer-to-peer networks.
XQuery 1.0 is nearing completion
Authors: Eisenberg Andrew , Melton Jim
Published: February 2006

XQuery is a query language designed for querying real and virtual XML documents and collections of these documents. Its development began in the second half of 1999. We provided an early look at XQuery in Dec. 2002 [1]. XQuery 1.0 is now approaching its publication as a W3C Recommendation, and we would like to update you on its progress. We can speak to this area with even more authority than we did last time, as we both became co-chairs of the W3C XML Query Working Group [2] in summer 2004.
Christos Faloutsos speaks out
Authors: Winslett Marianne
Published: February 2006

Welcome to this installment of ACM SIGMOD Record's series of interviews with distinguished members of the database community. I'm Marianne Winslett, and today I have here with me Christos Faloutsos, who is a professor of computer science at Carnegie Mellon University. Christos recieved the Presidential Young Investigator Award from the National Science Foundation in 1989. He received the 1997 VLDB Ten Year Paper Award for his paper on R+ trees, and the SIGMOD 1994 Best Paper Award for a paper on fast subsequence matching in time series databases. Christos is a member of the SIGKDD Executive Committee, and he has wide-ranging interests in data mining, database performance, and spatial and multimedia databases. His PhD is from the University of Toronto. So, Christos, welcome!
Changes to the
TODS
editorial board
Authors: Snodgrass Richard
Published: February 2006

The December issue should be out soon, if it isn't already. It is a special issue of papers invited from the SIGMOD'04 and PODS'04 conferences. I thank the authors, associate editors, and reviewers (some from the SIGMOD and PODS program committees) for writing, reviewing, revising, reviewing again, and then getting into final form these papers in the amazingly short time of eighteen months. This is a very nice issue, with seven substantive papers.
On quantum versions of record-breaking algorithms for SAT
Authors: Dantsin Evgeny , Kreinovich Vladik , Wolpert Alexander
Published: February 2006

It is well known that a straightforward application of Grover's quantum search algorithm enables to solve SAT in
O
(2

n
/2

) steps. Ambainis (SIGACT News, 2004) observed that it is possible to use Grover's technique to similarly speed up a sophisticated algorithm for solving 3-SAT. In this note, we show that a similar speed up can be obtained for all major record-breaking algorithms for satisfiability. We also show that if we use Grover's technique only, then we cannot do better than quadratic speed up.
A note on turing machine computability of rule driven systems
Authors: Kantorovitz Isaiah Pinchas
Published: February 2006

An abstract rule driven system is described. We prove that it is calculated by a restricted Turing Machine.
ACM SIGACT news distributed computing column 20
Authors: Rajsbaum Sergio
Published: February 2006

The Distributed Computing Column covers the theory of systems that are composed of a number of interacting computing elements. These include problems of communication and networking, databases, distributed shared memory, multiprocessor architectures, operating systems, verification, Internet, and the Web. This issue consists of:• "A review of the DISC 2005 conference," by Dariusz Kowalski.Many thanks to Dariusz for his contribution to this issue.
SIGACT news logic column 14
Authors: Pucella Riccardo
Published: February 2006

For this issue, James Cheney describes nominal logic, an approach to solve the problems involved with reasoning about bindings in formal languages that has been gaining in popularity in recent years, and surveys its major application areas.
Ten years of Forth in ACM Sigplan Notices
Authors: Frenger Paul
Published: February 2006

So here we are: ten years of the
ACM Sigplan Notices Forth Report
is behind us. How amazing it is that we have reached this milestone! I hope that this column's longevity is a reflection of its popularity and perceived value to our readers.
An improved algorithm for loop dead optimization
Authors: Behera Chandan Kumar , Kumar Pawan
Published: February 2006

Loop dead variables are the variables, which are defined in a loop, but not used in that loop. On successive execution of loop, these get different value, however all values (except last value) are not used. Hence in optimized program, the definition of a loop dead variable can be moved outside the loop (after the loop), rather than computing every time, inside the loop. In our discussion, we have assumed only simple loop. Every loop has one entry and one exit point.
Matrix-based component dependence representation and its applications in software quality assurance
Authors: Li Bixin , Zhou Ying , Wang Yancheng , Mo Junhui
Published: February 2006

Component dependence analysis is a useful technique that has many applications in software engineering activities including software understanding, testing, debugging, maintenance, and evolution. In this paper, we propose a matrix-based representation to analyze dependences in component-based system (CBSs). By further investigating the application of matrix in analyzing dependences of component-based system, we find that it has many applications in software quality assurance. To make it possible, we first identify all types of dependences in a CBS, and then present a dependence-based representation called the
component dependence graph
(CDG) and the
dependence matrix
(DM) to explicitly represent these dependences in a CBS. Based on the CDG and DM, we build a mathematical basis for managing and analyzing dependences in a CBS. Finally, we discuss some important applications of the dependence analysis technique in component-based software quality assurance, such as understanding, testing, maintenance, and evolution etc.
An ontology-based knowledge base for the representation and reuse of software patterns
Authors: Girardi Rosario , Lindoso Alisson Neres
Published: February 2006

The description, localization and effective reuse of software patterns and systems of patterns can be approached through an ontology-based formalism. An ontology is an explicit specification of objects, concepts and entities of an area of interest, besides the relationships between these concepts expressed through axioms. This work introduces ONTOPATTERN, an ontology that represents knowledge about how patterns are described and about their relationships in a pattern system. Patterns are included as instances of classes in the ontology, thus turning ONTOPATTERN a knowledge base where concepts are semantically related and where searches and inferences can be made thus facilitating the understanding and reuse of patterns. The use of ONTOPATTERN is illustrated through an example on the construction of a multi-agent framework.
Formally modelling software architectures with the UML 2.0 profile for π-ADL
Authors: Oquendo Flavio
Published: February 2006

A key aspect of the design of any software system is its architecture. An architecture description, from a runtime perspective, should provide a formal model of the architecture in terms of components and connectors, their ports and behaviours, and how they are composed together. The Unified Modelling Language (UML) is widely used in the design of software systems and has recently been extended to better support software architecture description. This paper presents the UML 2.0 Profile for π-ADL, a novel ADL that has been designed in the ArchWare European Project. It briefly presents π-ADL and its UML 2.0 Profile, then it illustrates through a case study how the UML 2.0 Profile for π-ADL can be used for formally modelling software architectures. The toolset for supporting the UML 2.0 Profile for π-ADL is outlined: it supports architecture modelling, architectural behaviour animation, and model checking of architectural properties.
Robustness analysis of cognitive information complexity measure using Weyuker properties
Authors: Kushwaha Dharmender Singh , Misra A. K.
Published: February 2006

Cognitive information complexity measure is based on cognitive informatics, which helps in comprehending the software characteristics. For any complexity measure to be robust, Weyuker properties must be satisfied to qualify as good and comprehensive one. In this paper, an attempt has also been made to evaluate cognitive information complexity measure in terms of nine Weyuker properties, through examples. It has been found that all the nine properties have been satisfied by cognitive information complexity measure and hence establishes cognitive information complexity measure based on information contained in the software as a robust and well-structured one.
A modified cognitive information complexity measure of software
Authors: Kushwaha Dharmender Singh , Misra A. K.
Published: February 2006

Most discipline of science have their own method of investigation built on foundation that is empirical and verifiable. Cognitive Informatics is no different. Cognitive Informatics is a field that studies internal information processing mechanism of the human brain and its application in software coding and computing. This paper attempts to empirically demonstrate the amount of information contained in software and develops a concept of cognitive information complexity measure based on the information contained in the software. It is found that software with higher cognitive information complexity measure has more information units contained in it. Therefore cognitive information complexity measure can be used to understand the cognitive information complexity and the information coding efficiency of the software.
How data inspection and consideration, provides for index compression and record access optimization of genetic databases
Authors: Zirkind Givon
Published: February 2006

With the many advances in computer hardware, the constant and historical challenges of optimization in processing and data storage diminished if not disappeared almost entirely. With hard drives getting larger and larger, while prices keep dropping; and the same occurring to memory; computer programs have turned more and more into bloatware. Likewise, processing speed has made efficiency and streamlining of program code, virtually a non-issue. The field of genetic research provides the perfect regeneration of those classical challenges to computer engineers. Genetic research requires extremely large databases, with extremely large indexes, with complex search criteria, with an extremely large number of inquiries and searches initiated remotely. Often, search requests are initiated over long geographic distances. To improve database performance, indexing access speed, and reduce index size, the author developed a new, genetic database, herein discussed.
Reminiscences
Authors: Wing Michael
Published: February 2006

My favorite column in ACM publications is the "Reminiscences on Influential Papers" in the SIGMOD Record. I don't know of anything else like it, anywhere. Each issue contains a handful of short essays (usually 2 or 3 long paragraphs), explaining why one research paper or another made an impression. Usually, the cited paper influenced the author's Ph.D. thesis or subsequent research.
Risks to the public
Authors: Neumann Peter G.
Published: February 2006

Edited by Peter G. Neumann (Risks Forum Moderator and Chairman of the ACM Committee on Computers and Public Policy), plus personal contributions by others, as indicated. Opinions expressed are individual rather than organizational, and all of the usual disclaimers apply. We address problems relating to software, hardware, people, and other circumstances relating to computer systems. To economize on space, we include pointers to items in the online Risks Forum: (R i j) denotes RISKS vol i number j. Cited RISKS items generally identify contributors and sources, together with URLs. Official RISKS archives are available at www.risks.org (which redirects to Newcastle and gets you nice html formatting and a search engine courtesy of Lindsay Marshall; http://catless.ncl.ac.uk/Risks/i.j.html gets you (R i j)) and at ftp://www.sri.com/risks.
PASTE at Microsoft
Authors: Das Manuvir
Published: February 2006

The Windows division of Microsoft Corporation is in the midst of a massive effort to improve the security and reliability of the next release of the product - Windows Vista. In this talk, I will explain how the Center for Software Excellence at Microsoft has used program analysis technology to build the tools that enable this effort. Along the way, I will cover the current Windows engineering process and the role of the tools in the process, the core program analysis techniques we have invented and used in the tools, business and environment issues that govern the engineering process, and research directions suggested by our experience so far.
Evaluating the impact of context-sensitivity on Andersen's algorithm for Java programs
Authors: Liang Donglin , Pennings Maikel , Harrold Mary Jean
Published: February 2006

Program analysis and program optimization of Java programs require reference information that estimates the instances of classes that may be accessed through dereferences. Recent work has presented several approaches for adapting Andersen's algorithm [1]---the most precise flow-insensitive and context-insensitive points-to analysis algorithm developed for C--- for analyzing Java programs (e.g., [5, 9, 12]). Studies in our previous work [6] indicate that this algorithm may compute very imprecise reference information for Java programs.
Link-time static analysis for efficient separate compilation of object-oriented languages
Authors: Privat Jean , Ducournau Roland
Published: February 2006

Compilers used in industry are mainly based on a separate compilation framework. However, the knowledge of the whole program improves efficiency of object-oriented language compilers, therefore more efficient implementation techniques are based on a global compilation framework.In this paper, we propose a compromise by including three global compilation techniques (type analysis, coloring and binary tree dispatching) in a separate compilation framework. Files are independently compiled into standard binary files with unresolved symbols. The program is build by linking object files: files are gathered and analyzed, some link code is generated then symbols are resolved.
Low overhead program monitoring and profiling
Authors: Kumar Naveen , Childers Bruce R. , Soffa Mary Lou
Published: February 2006

Program instrumentation, inserted either before or during execution, is rapidly becoming a necessary component of many systems. Instrumentation is commonly used to collect information for many diverse analysis applications, such as detecting program invariants, dynamic slicing and alias analysis, software security checking, and computer architecture modeling. Because instrumentation typically has a high run-time overhead, techniques are needed to mitigate the overheads. This paper describes "instrumentation optimizations" that reduce the overhead of profiling for program analysis. Our approach applies transformations to the instrumentation code that reduce the (1) number of instrumentation points executed, (2) cost of instrumentation probes, and (3) cost of instrumentation payload, while maintaining the semantics of the original instrumentation. We present the transformations and apply them for program profiling and computer architecture modeling. We evaluate the optimizations and show that the optimizations improve profiling performance by 1.26-2.63x and architecture modeling performance by 2-3.3x.
A concept analysis inspired greedy algorithm for test suite minimization
Authors: Tallam Sriraman , Gupta Neelam
Published: February 2006

Software testing and retesting occurs continuously during the software development lifecycle to detect errors as early as possible and to ensure that changes to existing software do not break the software. Test suites once developed are reused and updated frequently as the software evolves. As a result, some test cases in the test suite may become redundant as the software is modified over time since the requirements covered by them are also covered by other test cases. Due to the resource and time constraints for re-executing large test suites, it is important to develop techniques to minimize available test suites by removing redundant test cases. In general, the test suite minimization problem is NP complete. In this paper, we present a new greedy heuristic algorithm for selecting a minimal subset of a test suite
T
that covers all the requirements covered by
T.
We show how our algorithm was inspired by the concept analysis framework. We conducted experiments to measure the extent of test suite reduction obtained by our algorithm and prior heuristics for test suite minimization. In our experiments, our algorithm always selected same size or smaller size test suite than that selected by prior heuristics and had comparable time performance.
MonDe
Authors: Cook Jonathan , Orso Alessandro
Published: February 2006

Safely updating software at remote sites is a cautious balance of enabling new functionality and avoiding adverse effects on existing functionality. A useful first step in this process would be to evaluate the performance of a new version of a component on the current workload before enabling its functionality. This step would let the engineers assess the component's performance over more (and more realistic) data points than by simply performing regression testing in-house.In this paper we propose to evaluate the performance of a new version of a component by (1) deploying it to remote sites, (2) running it in a controlled environment with the actual workloads being generated at that site, and (3) reporting the results back to the development engineers. Running the new version can either be done on-line, alongside the current system, or offline, using capture-replay techniques. By running at the remote site and reporting concise results, issues of data security, protection, and confidentiality are diminished, yet the new version can be evaluated on real workloads.
Invariants and state in testing and formal methods
Authors: Hamlet Dick
Published: February 2006

Logical formulas called invariants are a staple of formal methods for program analysis. Persistent-state variables appear in these formulas playing their proper intuitive role, which is somewhere between inputs and internal variables. In software testing theory, on the contrary, state is not usually accorded explicit treatment. Comparing the viewpoints of formal methods and testing theory suggests new roles that formal methods can play in testing. This examination is motivated by recent systems such as Daikon, which use both tests and invariants.
Symbolic path simulation in path-sensitive dataflow analysis
Authors: Hampapuram Hari , Yang Yue , Das Manuvir
Published: February 2006

Symbolic path simulation is becoming an increasingly important component in many static analysis tasks. The emergence of inter-procedural path-sensitive dataflow algorithms has both raised the demands and posed new challenges for effective techniques in path feasibility analysis.This paper develops a general-purpose path simulator and applies it to support path-sensitive dataflow analysis. The core component of the path simulator is a simulation engine that supports a wide variety of programming language features. This simulation engine can be "wrapped" with an interface layer to support a given client application.As a concrete case study, we discuss the experiences gained in integrating the path simulator with ESP, a software validation tool for C/C++ programs. We apply ESP to validate a future version of Windows against critical security properties. Our results show that the global path simulation mechanism is both critical in improving precision and scalable enough to be of practical use.
SableSpMT
Authors: Pickett Christopher J. F. , Verbrugge Clark
Published: February 2006

Speculative multithreading (SpMT) is a promising optimisation technique for achieving faster execution of sequential programs on multiprocessor hardware. Analysis of and data acquisition from such systems is however difficult and complex, and is typically limited to a specific hardware design and simulation environment. We have implemented a flexible, software-based speculative multithreading architecture within the context of a full-featured Java virtual machine. We consider the entire Java language and provide a complete set of support features for speculative execution, including return value prediction. Using our system we are able to generate extensive dynamic analysis information, analyse the effects of runtime feedback, and determine the impact of incorporating static, offline information. Our approach allows for accurate analysis of Java SpMT on existing, commodity multiprocessor hardware, and provides a vehicle for further experimentation with speculative approaches and optimisations.
Representation-independent program analysis
Authors: Strout Michelle Mills , Mellor-Crummey John , Hovland Paul
Published: February 2006

Program analysis has many applications in software engineering and high-performance computation, such as program understanding, debugging, testing, reverse engineering, and optimization. A ubiquitous compiler infrastructure does not exist; therefore, program analysis is essentially reimplemented for each compiler infrastructure. The goal of the OpenAnalysis toolkit is to separate analysis from the intermediate representation (IR) in a way that allows the orthogonal development of compiler infrastructures and program analysis. Separation of analysis from specific IRs will allow faster development of compiler infrastructures, the ability to share and compare analysis implementations, and in general quicker breakthroughs and evolution in the area of program analysis. This paper presents how we are separating analysis implementations from IRs with analysis-specific, IR-independent interfaces. Analysis-specific IR interfaces for alias/pointer analysis algorithms and reaching constants illustrate that an IR interface designed for language dependence is capable of providing enough information to support the implementation of a broad range of analysis algorithms and also represent constructs within many imperative programming languages.
LANCET
Authors: Van Put Ludo , De Sutter Bjorn , Madou Matias , De Bus Bruno , Chanet Dominique , Smits Kristof , De Bosschere Koen
Published: February 2006

This paper presents LANCET, a multi-platform software visualization tool that enables the inspection of programs at the binary code level. Implemented on top of the link-time rewriting framework DIABLO, LANCET provides several views on the interprocedural control flow graph of a program. These views can be used to navigate through the program, to edit the program in a efficient manner, and to interact with the existing whole-program analyses and optimizations that are implemented in DIABLO or existing applications of DIABLO. As such, LANCET is an ideal tool to examine compiler-generated code, to assist the development of new compiler optimizations, or to optimize assembly code manually.
Generalizing symbolic execution to library classes
Authors: Khurshid Sarfraz , Suen Yuk Lai
Published: February 2006

Forward symbolic execution is a program analysis technique that allows using symbolic inputs to explore program executions. The traditional applications of this technique have focused on programs that manipulate primitive data types, such as integer or boolean. Recent extensions have shown how to handle reference types at their representation level. The extensions have favorably been backed by advances in constraint solving technology, and together they have made symbolic execution applicable, at least in theory, to a large class of programs. In practice, however, the increased potential for applications has created significant issues with scalability of symbolic execution to programs of non-trivial size---the ensuing path conditions rapidly become unfeasibly complex.We present Dianju, a new technique that aims to address the scalability of symbolic execution. The fundamental idea in Dianju is to perform symbolic execution of commonly used library classes (such as strings, sets and maps) at the abstract level rather than the representation level. Dianju defines semantics of operations on symbolic objects of these classes, which allows Dianju to abstract away from the complexity that is normally inherent in library implementations, thus promising scalable analyses based on symbolic execution.
Formal model and policy specification of usage control
Authors: Zhang Xinwen , Parisi-Presicce Francesco , Sandhu Ravi , Park Jaehong
Published: February 2006

The recent usage control model (UCON) is a foundation for next-generation access control models with distinguishing properties of decision continuity and attribute mutability. A usage control decision is determined by combining authorizations, obligations, and conditions, presented as
UCON

ABC

core models by Park and Sandhu. Based on these core aspects, we develop a formal model and logical specification of UCON with an extension of Lamport's temporal logic of actions (TLA). The building blocks of this model include: (1) a set of sequences of system states based on the attributes of subjects, objects, and the system, (2) authorization predicates based on subject and object attributes, (3) usage control actions to update attributes and accessing status of a usage process, (4) obligation actions, and (5) condition predicates based on system attributes. A usage control policy is defined as a set of temporal logic formulas that are satisfied as the system state changes. A fixed set of scheme rules is defined to specify general UCON policies with the properties of soundness and completeness. We show the flexibility and expressive capability of this formal model by specifying the core models of UCON and some applications.
Power reduction techniques for microprocessor systems
Authors: Venkatachalam Vasanth , Franz Michael
Published: February 2006

Power consumption is a major factor that limits the performance of computers. We survey the “state of the art” in techniques that reduce the total power consumed by a microprocessor system over time. These techniques are applied at various levels ranging from circuits to architectures, architectures to system software, and system software to applications. They also include holistic approaches that will become more important over the next decade. We conclude that power management is a multifaceted discipline that is continually expanding with new techniques being developed at every level. These techniques may eventually allow computers to break through the “power wall” and achieve unprecedented levels of performance, versatility, and reliability. Yet it remains too early to tell which techniques will ultimately solve the power problem.
A parallel, incremental, mostly concurrent garbage collector for servers
Authors: Barabash Katherine , Ben-Yitzhak Ori , Goft Irit , Kolodner Elliot K. , Leikehman Victor , Ossia Yoav , Owshanko Avi , Petrank Erez
Published: February 2006

Multithreaded applications with multigigabyte heaps running on modern servers provide new challenges for garbage collection (GC). The challenges for “server-oriented” GC include: ensuring short pause times on a multigigabyte heap while minimizing throughput penalty, good scaling on multiprocessor hardware, and keeping the number of expensive multicycle fence instructions required by weak ordering to a minimum.We designed and implemented a collector facing these demands building on the mostly concurrent garbage collector proposed by Boehm et al. [1991]. Our collector incorporates new ideas into the original collector. We make it parallel and incremental; we employ concurrent low-priority background GC threads to take advantage of processor idle time; we propose novel algorithmic improvements to the basic mostly concurrent algorithm improving its efficiency and shortening its pause times; and finally, we use advanced techniques, such as a low-overhead work packet mechanism to enable full parallelism among the incremental and concurrent collecting threads and ensure load balancing.We compared the new collector to the mature, well-optimized, parallel, stop-the-world mark-sweep collector already in the IBM JVM. When allowed to run aggressively, using 72% of the CPU utilization during a short concurrent phase, our collector prototype reduces the maximum pause time from 161 ms to 46 ms while only losing 11.5% throughput when running the SPECjbb2000 benchmark on a 600-MB heap on an 8-way PowerPC 1.1-GHz processors. When the collector is limited to a nonintrusive operation using only 29% of the CPU utilization, the maximum pause time obtained is 79 ms and the loss in throughput is 15.4%.
Termination analysis and specialization-point insertion in offline partial evaluation
Authors: Glenstrup Arne John , Jones Neil D.
Published: February 2006

Recent research suggests that the goal of fully automatic and reliable program generation for a broad range of applications is coming nearer to feasibility. However, several interesting and challenging problems remain to be solved before it becomes a reality. Solving them is alsonecessary,if we hope ever to elevate software engineering from its current state (a highly developed handiwork) into a successful branch of engineering, capable of solving a wide range of new problems by systematic, well-automated and well-founded methods.A key problem in all program generation isterminationof the generation process. This article focuses on off-line partial evaluation and describes recent progress towards automatically solving the termination problem, first for individual programs, and then for specializers and “generating extensions,” the program generators that most offline partial evaluators produce.The technique is based onsize-change graphsthat approximate the changes in parameter sizes at function calls. We formulate a criterion,bounded anchoring,for detecting parameters known to be bounded during specialization: a bounded parameter can act as ananchorfor other parameters. Specialization points necessary for termination are computed by adding a parameter that tracks call depth, and then selecting a specialization point in every call loop where it is unanchored. By generalizing all unbounded parameters, we compute a binding-time division which together with the set of specialization pointsguaranteestermination.Contributions of this article include a proof, based on the operational semantics of partial evaluation with memoization, that the analysis guarantees termination; and an in-depth description of safety of the increasing size approximation operator required for termination analysis in partial evaluation.Initial experiments with a prototype shows that the analysis overall yields binding-time divisions that can achieve a high degree of specialization, while still guaranteeing termination.The article ends with a list of challenging problems whose solution would bring the community closer to the goal of broad-spectrum, fully automatic and reliable program generation.
A theory of overloading
Authors: Stuckey Peter J. , Sulzmann Martin
Published: February 2006

We present a novel approach to allow for overloading of identifiers in the spirit of type classes. Our approach relies on a combination of the HM(X) type system framework with Constraint Handling Rules (CHRs). CHRs are a declarative language for writing incremental constraint solvers, that provide our scheme with a form of programmable type language. CHRs allow us to precisely describe the relationships among overloaded identifiers. Under some sufficient conditions on the CHRs we achieve decidable type inference and the semantic meaning of programs is unambiguous. Our approach provides a common formal basis for many type class extensions such as multiparameter type classes and functional dependencies.
Implicit-signal monitors
Authors: Buhr Peter A. , Harji Ashif S.
Published: February 2006

An implicit (automatic) signal monitor uses a
waituntil
predicate
statement to construct synchronization, as opposed to an explicit-signal monitor using condition variables and
signal/wait
statements for synchronization. Of the two synchronization approaches, the implicit-signal monitor is often easier to use and prove correct, but has an inherently high execution cost. Hence, its primary use is for prototyping concurrent systems using monitors, where speed and accuracy of software development override execution performance. After a concurrent system is working, any implicit-signal monitor that is a performance bottleneck can be converted to an explicit-signal monitor. Unfortunately, many monitor-based concurrency systems provide only explicit-signal monitors, precluding the design benefits of implicit-signal monitors.This article presents a historical look at the development of the implicit-signal monitor in relation to its counterpart the explicit-signal monitor. An analysis of the different kinds of implicit-signal monitors shows the effects certain design decisions have on the problems that can be solved and the performance of the solutions. Finally, an extensive discussion is presented on simulating an implicit-signal monitor via different explicit-signal monitors. These simulations are reasonably complex, depending on the kind of explicit-signal monitor available for the simulation and the desired semantics required for the implicit-signal monitor. Interestingly, the complexity of the simulations also illustrates certain deficiencies with explicit-signal monitors, which are discussed in detail. Performance comparisons are made among the different simulations with monitors from the concurrent systems PThreads, Java, and μC++.
Birrell's distributed reference listing revisited
Authors: Moreau Luc , Dickman Peter , Jones Richard
Published: February 2006

The Java RMI collector is arguably the most widely used distributed garbage collector. Its distributed reference listing algorithm was introduced by Birrell et al. in the context of Network Objects, where the description was informal and heavily biased toward implementation. In this article, we formalize this algorithm in an implementation-independent manner, which allows us to clarify weaknesses of the initial presentation. In particular, we discover cases critical to the correctness of the algorithm that were not accounted for by Birrell. We use our formalization to derive an invariant-based proof of correctness of the algorithm that avoids notoriously difficult temporal reasoning. Furthermore, we offer a novel graphical representation of the state transition diagram, which we use to provide intuitive explanations of the algorithm and to investigate its tolerance to faults in a systematic manner. Finally, we examine how the algorithm may be optimized, either by placing constraints on message channels or by tightening the coupling between the application program and distributed garbage collector.
The next frontier of users' preferences
Authors: Vitali Fabio
Published: February 2006

What do you do when you notice a blatant error on a Web page? Write the author? Ignore it? Chalk it up to ignorance? If I feel the error is important---whether or not I think the webmaster is likely to listen to me---I may go looking for an address. But honestly, don't you sometimes wish you could just make the change yourself? In this Whiteboard, Fabio Vitali explores cross-editing and the emerging technology that may make this possible... or seem to be possible...

This will be the last Whiteboard. Although I'll miss it, after six years it's time to do something different.

---Elizabeth Buie
XFM
Authors: Suhaib Syed M. , Mathaikutty Deepak A. , Shukla Sandeep K. , Berner David
Published: February 2006

We present an agile formal methodology named eXtreme Formal Modeling (XFM), based on Extreme Programming (XP) concepts to construct abstract models from natural language specifications of complex systems. In particular, we focus on Prescriptive Formal Models (PFMs) that capture the specification of the system under design in a mathematically precise manner. Such models can be used as golden reference models for formal verification, test generation, coverage monitor generation, etc. This methodology for incrementally building PFMs works by adding
user stories
expressed as LTL formulae gleaned from the natural language specifications, one by one, into the model. XFM builds the models, retaining correctness with respect to incrementally added properties by regressively model-checking all the LTL properties captured theretofore in the model. We illustrate XFM with a graded set of examples consisting of a traffic light controller and a DLX pipeline. To make the regressive model-checking steps feasible with current model-checking tools, we need to control the model size increments at each subsequent step in the process. We therefore analyze the effects of ordering the LTL properties in XFM on the statespace growth rate of the model. We compare three different property-ordering methodologies: ad hoc ordering, property-based ordering, and predicate-based ordering. We experiment on the models of the ISA bus monitor and the arbitration phase of the Pentium Pro bus. We experimentally show and mathematically reason that the predicate-based ordering is the best among these orderings. Finally, we present a GUI-based toolbox that we implemented to build PFMs using XFM.