bluuebunny/crossref_metadata_2025 huggingface dataset:
METRIC
Authors: Marathe Jaydeep , Mueller Frank , Mohan Tushar , Mckee Sally A. , De Supinski Bronis R. , Yoo Andy
Published: June 2007

With the diverging improvements in CPU speeds and memory access latencies, detecting and removing memory access bottlenecks becomes increasingly important. In this work we present METRIC, a software framework for isolating and understanding such bottlenecks using partial access traces. METRIC extracts access traces from executing programs without special compiler or linker support. We make four primary contributions. First, we present a framework for extracting partial access traces based on dynamic binary rewriting of the executing application. Second, we introduce a novel algorithm for compressing these traces. The algorithm generates constant space representations for regular accesses occurring in nested loop structures. Third, we use these traces for offline incremental memory hierarchy simulation. We extract symbolic information from the application executable and use this to generate detailed source-code correlated statistics including per-reference metrics, cache evictor information, and stream metrics. Finally, we demonstrate how this information can be used to isolate and understand memory access inefficiencies. This illustrates a potential advantage of METRIC over compile-time analysis for sample codes, particularly when interprocedural analysis is required.
Polychronous design of embedded real-time applications
Authors: Gamatié Abdoulaye , Gautier Thierry , Guernic Paul Le , Talpin Jean-Pierre
Published: June 2007

Embedded real-time systems consist of hardware and software that controls the behavior of a device or plant. They are ubiquitous in today's technological landscape and found in domains such as telecommunications, nuclear power, avionics, and medical technology. These systems are difficult to design and build because they must satisfy both functional and timing requirements to work correctly in their intended environment. Furthermore, embedded systems are often critical systems, where failure can lead to loss of life, loss of mission, or serious financial consequences. Because of the difficulty in creating these systems and the consequences of failure, they require rigorous and reliable design approaches. The synchronous approach is one possible answer to this demand. Its mathematical basis provides formal concepts that favor the trusted design of embedded real-time systems. The multiclock or
polychronous
model stands out from other synchronous specification models by its capability to enable the design of systems where each component holds its own activation clock as well as single-clocked systems in a uniform way. A great advantage is its convenience for component-based design approaches that enable modular development of increasingly complex modern systems. The expressiveness of its underlying semantics allows dealing with several issues of real-time design. This article exposes insights gained during recent years from the design of real-time applications within the polychronous framework. In particular, it shows promising results about the design of applications from the avionics domain.
On the maximum satisfiability of random formulas
Authors: Achlioptas Dimitris , Naor Assaf , Peres Yuval
Published: June 2007

Say that a
k
-CNF a formula is
p-satisfiable
if there exists a truth assignment satisfying a fraction 1 − 2

−
k

+
p
2

−
k

of its clauses (note that every
k
-CNF formula is 0-satisfiable). Let
F

k

(
n
,
m
) denote a random
k
-CNF formula on
n
variables with
m
clauses. For every
k
≥2 and every
r
>0 we determine
p
and δ=δ(
k
)=
O
(
k
2

−
k
/2

) such that with probability tending to 1 as
n
→∞, a random
k
-CNF formula
F
k
(
n
,
rn
) is
p
-satisfiable but not (
p
+δ)-satisfiable.
Asymptotics and fast simulation for tail probabilities of maximum of sums of few random variables
Authors: Juneja S. , Karandikar R. L. , Shahabuddin P.
Published: June 2007

We derive tail asymptotics for the probability that the maximum of sums of a few random variables exceeds an increasing threshold, when the random variables may be light as well as heavy tailed. These probabilities arise in many applications including in PERT networks where our interest may be in measuring the probability of large project delays. We also develop provably asymptotically optimal importance sampling techniques to efficiently estimate these probabilities. In the light-tailed settings we show that an appropriate mixture of exponentially twisted distributions efficiently estimates these probabilities. As is well known, exponential twisting based methods are not applicable in the heavy-tailed settings. To remedy this, we develop techniques that rely on “asymptotic hazard rate twisting” and prove their effectiveness in both light and heavy-tailed settings. We show that in many cases the latter may have implementation advantages over exponential twisting based methods in the light-tailed settings. However, our experiments suggest that when easily implementable, the exponential twisting based methods significantly outperform asymptotic hazard rate twisting based methods.
Recycling computed answers in rewrite systems for abduction
Authors: Lin Fangzhen , You Jia-Huai
Published: June 2007

In rule-based systems, goal-oriented computations correspond naturally to the possible ways that an observation may be explained. In some applications, we need to compute explanations for a series of observations with the same domain. The question arises as to whether previously computed answers can be recycled. A “yes” answer could result in substantial savings of repeated computations. For systems based on classical logic, the answer
is
yes. For nonmonotonic systems, however, one tends to believe that the answer should be
no
, since recycling is a form of adding information. In this article, we show that computed answers can always be recycled, in a nontrivial way, for the class of rewrite procedures proposed earlier by the authors for logic programs with negation. We present some experimental results on an encoding of the logistics domain.
On the reliability of factoid question answering evaluation
Authors: Sakai Tetsuya
Published: June 2007

This paper compares some existing evaluation metrics for factoid question answering (QA) from the viewpoint of stability and sensitivity, using the NTCIR-4 QAC2 Japanese factoid QA tasks and the Buckley/Voorhees stability method and Voorhees/Buckley swap method. Our main findings are: (1) For QA evaluation with ranked lists containing up to five answers, the fraction of questions with a correct answer within top 5 (NQcorrect5) and that with a correct answer at rank 1 (NQcorrect1) are not as stable and sensitive as reciprocal rank. (2) Q-measure, which can handle multiple correct answers and answer correctness levels, is at least as stable and sensitive as reciprocal rank, provided that a
mild
gain value assignment is used. Emphasizing answer correctness levels tends to hurt stability and sensitivity, while handling multiple correct answers improves them. As our experimental methods are language-independent, we believe that these findings apply to QA in languages other than Japanese as well.
Conjugation-based compression for Hebrew texts
Authors: Wiseman Yair , Gefner Irit
Published: June 2007

Traditional compression techniques do not look deeply into the morphology of languages. This can be less critical in languages like English where most of the sequences are illegal according to the grammatical rules of the language, for example, zx, bv or qe; hence the morphology can add a little information that can be beneficial for the compression algorithm. However, this negligence can be a significant flaw in languages like Hebrew where the grammatical rules allow much more freedom in the sequences of letters and, except tet after gimel, any pair is legal; hence compressing without taking the morphological rules into account can yield a poorer compression ratio. This article suggests a tool that optimizes the Burrows-Wheeler algorithm which is an unaware morphological rules compression method. It first preprocesses a Hebrew text file according to the Hebrew conjugation rules, and, after that, it provides the Burrows-Wheeler algorithm with this preprocessed file so that can be compressed better. Experimental results show a significant improvement.
A field evaluation of an adaptable two-interface design for feature-rich software
Authors: McGrenere Joanna , Baecker Ronald M. , Booth Kellogg S.
Published: June 2007

Two approaches for supporting personalization in complex software are system-controlled adaptive menus and user-controlled adaptable menus. We evaluate a novel interface design for feature-rich productivity software based on adaptable menus. The design allows the user to easily customize a personalized interface, and also supports quick access to the default interface with all of the standard features. This design was prototyped as a front-end to a commercial word processor. A field experiment investigated users' personalizing behavior and tested the effects of different interface designs on users' satisfaction and their perceived ability to navigate, control, and learn the software. There were two conditions: a commercial word processor with adaptive menus and our prototype with adaptable menus for the same word processor. Our evaluation shows: (1) when provided with a flexible, easy-to-use and easy-to-understand customization mechanism, the majority of users do effectively personalize their interface; and (2) user-controlled interface adaptation with our adaptable menus results in better navigation and learnability, and allows for the adoption of different personalization strategies, as compared to a particular system-controlled adaptive menu system that implements a single strategy. We report qualitative data obtained from interviews and questionnaires with participants in the evaluation in addition to quantitative data.
A model-based extensible framework for efficient application design using FPGA
Authors: Mohanty Sumit , Prasanna Viktor K.
Published: June 2007

For an FPGA designer, several choices are available in terms of target FPGA devices, IP-cores, algorithms, synthesis options, runtime reconfiguration, degrees of parallelism, among others, while implementing a design. Evaluation of design alternatives in the early stages of the design cycle is important because the choices made can have a critical impact on the performance of the final design. However, a large number of alternatives not only results in a large number of designs, but also makes it a hard problem to efficiently manage, simulate, and evaluate them. In this article, we present a framework for FPGA-based application design that addresses the aforementioned issues. This framework supports a hierarchical modeling approach that integrates application and device modeling techniques and allows development of a library of models for design reuse. The framework integrates a high-level performance estimator for rapid estimation of the latency, area, and energy of the designs. In addition, a design space exploration tool allows efficient evaluation of candidate designs against the given performance requirements. The framework also supports extension through integration of widely used tools for FPGA-based design while presenting a unified environment for different target FPGAs. We demonstrate our framework through the modeling and performance estimation of a signal processing kernel and the design of end-to-end applications.
A predictive decode filter cache for reducing power consumption in embedded processors
Authors: Tang Weiyu , Kejariwal Arun , Veidenbaum Alexander V. , Nicolau Alexandru
Published: June 2007

With advances in semiconductor technology, power management has increasingly become a very important design constraint in processor design. In embedded processors, instruction fetch and decode consume more than 40% of processor power. This calls for development of power minimization techniques for the fetch and decode stages of the processor pipeline. For this, filter cache has been proposed as an architectural extension for reducing the power consumption. A filter cache is placed between the CPU and the instruction cache (I-cache) to provide the instruction stream. A filter cache has the advantages of shorter access time and lower power consumption. However, the downside of a filter cache is a possible performance loss in case of cache misses.

In this article, we present a novel technique---decode filter cache (DFC)---for minimizing power consumption with minimal performance impact. The DFC stores decoded instructions. Thus, a hit in the DFC eliminates instruction fetch and its subsequent decoding. The bypassing of both instruction fetch and decode reduces processor power. We present a runtime approach for predicting whether the next fetch source is present in the DFC. In case a miss is predicted, we reduce the miss penalty by accessing the I-cache directly. We propose to classify instructions as cacheable or noncacheable, depending on the decode width. For efficient use of the cache space, a sectored cache design is used for the DFC so that both cacheable and noncacheable instructions can coexist in the DFC sector. Experimental results show that the DFC reduces processor power by 34% on an average and our next fetch prediction mechanism reduces miss penalty by more than 91%.
DRDU
Authors: Issenin Ilya , Brockmeyer Erik , Miranda Miguel , Dutt Nikil
Published: June 2007

In multimedia and other streaming applications, a significant portion of energy is spent on data transfers. Exploiting data reuse opportunities in the application, we can reduce this energy by making copies of frequently used data in a small local memory and replacing speed- and power-inefficient transfers from main off-chip memory by more efficient local data transfers. In this article we present an automated approach for analyzing these opportunities in a program that allows modification of the program to use custom scratch-pad memory configurations comprising a hierarchical set of buffers for local storage of frequently reused data. Using our approach we are able to both reduce energy consumption of the memory subsystem when using a scratch-pad memory by about a factor of two, on average, and improve memory system performance compared to a cache of the same size.
Low test application time resource binding for behavioral synthesis
Authors: Hosseinabady Mohammad , Lotfi-Kamran Pejman , Navabi Zainalabedin
Published: June 2007

Recent advances in process technology have led to a rapid increase in the density of integrated circuits (ICs). Increased density and the need to test for new types of defects in nanometer technologies have resulted in a tremendous increase in test application time (TAT). This article presents a test synthesis method to reduce test application time for testing the datapath of a design. The test application time is reduced by applying a test-time-aware resource sharing algorithm on a scheduled control data flow graph (CDFG) of a design.
Online audio background determination for complex audio environments
Authors: Moncrieff Simon , Venkatesh Svetha , West Geoff
Published: June 2007

We present a method for foreground/background separation of audio using a background modelling technique. The technique models the background in an online, unsupervised, and adaptive fashion, and is designed for application to long term surveillance and monitoring problems. The background is determined using a statistical method to model the states of the audio over time. In addition, three methods are used to increase the accuracy of background modelling in complex audio environments. Such environments can cause the failure of the statistical model to accurately capture the background states. An entropy-based approach is used to unify background representations fragmented over multiple states of the statistical model. The approach successfully unifies such background states, resulting in a more robust background model. We adaptively adjust the number of states considered background according to background complexity, resulting in the more accurate classification of background models. Finally, we use an auxiliary model cache to retain potential background states in the system. This prevents the deletion of such states due to a rapid influx of observed states that can occur for highly dynamic sections of the audio signal. The separation algorithm was successfully applied to a number of audio environments representing monitoring applications.
A piano duo support system for parents to lead children to practice musical performances
Authors: Oshima Chika , Nishimoto Kazushi , Hagita Norihiro
Published: June 2007

In this article, we propose “Family Ensemble,” a piano duo support system for a musically inept parent and his/her child who is a beginner at playing the piano. The system makes it easier for parents to correctly reproduce a given sequence of pitches along with the child's performance by using score tracking and note-replacement functions. The experiments with this support system showed that the parents can immediately participate in the piano duo. Furthermore, we found that during joint practices using Family Ensemble some subjects discussed musical ideas that they would not have talked about without using the system.
A history of ACM SIGGRAPH
Authors: Brown Judy , Cunningham Steve
Published: June 2007

From a small group of like-minded scientists drawn to the dynamics of computer-generated images to a driving force in computer graphics bringing together thousands from around the world, SIGGRAPH continues to chart the course for this diverse and ever-changing field.
SIGCOMM's archaeological journey into networking's past
Authors: Edmondson-Yurkanan Chris
Published: June 2007

Documenting the technical history of a SIG is indeed a priceless resource.
The software architect
Authors: McBride Matthew R.
Published: June 2007

Leadership is the defining characteristic in an unforgiving technology arena.
The pearly gates of Internet TV
Authors: Shannon Meg McGinity
Published: June 2007

Is this a marriage made in heaven?
The rime of the ancyent programmer
Authors: Jenkins Stephen B.
Published: June 2007

How one programmer's career, set adrift on the raging seas of technological change, has been tossed by the winds of fate.
One man's quest for the state of software engineering's practice
Authors: Glass Robert L.
Published: June 2007

Analyzing researchers' findings of software practitioners' activities.
The WaveScalar architecture
Authors: Swanson Steven , Schwerin Andrew , Mercaldi Martha , Petersen Andrew , Putnam Andrew , Michelson Ken , Oskin Mark , Eggers Susan J.
Published: June 2007

Silicon technology will continue to provide an exponential increase in the availability of raw transistors. Effectively translating this resource into application performance, however, is an open challenge that conventional superscalar designs will not be able to meet. We present WaveScalar as a scalable alternative to conventional designs. WaveScalar is a dataflow instruction set and execution model designed for scalable, low-complexity/high-performance processors. Unlike previous dataflow machines, WaveScalar can efficiently provide the sequential memory semantics that imperative languages require. To allow programmers to easily express parallelism, WaveScalar supports pthread-style, coarse-grain multithreading and dataflow-style, fine-grain threading. In addition, it permits blending the two styles within an application, or even a single function.

To execute WaveScalar programs, we have designed a scalable, tile-based processor architecture called the WaveCache. As a program executes, the WaveCache maps the program's instructions onto its array of processing elements (PEs). The instructions remain at their processing elements for many invocations, and as the working set of instructions changes, the WaveCache removes unused instructions and maps new ones in their place. The instructions communicate directly with one another over a scalable, hierarchical on-chip interconnect, obviating the need for long wires and broadcast communication.

This article presents the WaveScalar instruction set and evaluates a simulated implementation based on current technology. For single-threaded applications, the WaveCache achieves performance on par with conventional processors, but in less area. For coarse-grain threaded applications the WaveCache achieves nearly linear speedup with up to 64 threads and can sustain 7--14 multiply-accumulates per cycle on fine-grain threaded versions of well-known kernels. Finally, we apply both styles of threading to
equake
from Spec2000 and speed it up by 9x compared to the serial version.
Reducing branch predictor leakage energy by exploiting loops
Authors: Zhang Wei , Allu Bramha
Published: June 2007

With the scaling of technology, leakage energy will become the dominant source of energy consumption. Besides cache memories, branch predictors are among the largest on-chip array structures and consume nontrivial leakage energy. This paper proposes two cost-effective loop-based strategies to reduce the branch predictor leakage without impacting prediction accuracy or performance. The loop-based approaches exploit the fact that loops usually only contain a small number of instructions and, hence, even fewer branch instructions while taking a significant fraction of the execution time. Consequently, all the nonactive entries of branch predictors can be placed into the low leakage mode during the loop execution in order to reduce leakage energy. Compiler and circuit supports are discussed to implement the proposed leakage-reduction strategies. Compared to the recently proposed decay-based approach, our experimental results show that the loop-based approach can extract 16.2% more dead time of the branch predictor, on average, leading to more leakage energy savings without impacting the branch prediction accuracy and performance.
Beyond single-appearance schedules
Authors: Ko Ming-Yung , Murthy Praveen K. , Bhattacharyya Shuvra S.
Published: June 2007

Synthesis of digital signal-processing (DSP) software from dataflow-based formal models is an effective approach for tackling the complexity of modern DSP applications. In this paper, an efficient method is proposed for applying subroutine call instantiation of module functionality when synthesizing embedded software from a dataflow specification. The technique is based on a novel recursive decomposition of subgraphs in a cluster hierarchy that is optimized for low buffer size. Applying this technique, one can achieve significantly lower buffer sizes than what is available for minimum code size inlined schedules, which have been the emphasis of prior work on software synthesis. Furthermore, it is guaranteed that the number of procedure calls in the synthesized program is polynomially bounded in the size of the input dataflow graph, even though the number of module invocations may increase exponentially. This recursive decomposition approach provides an efficient means for integrating subroutine-based module instantiation into the design space of DSP software synthesis. The experimental results demonstrate a significant improvement in buffer cost, especially for more irregular multirate DSP applications, with moderate code and execution time overhead.
On mutually exclusive roles and separation-of-duty
Authors: Li Ninghui , Tripunitara Mahesh V. , Bizri Ziad
Published: June 2007

Separation-of-duty (SoD) is widely considered to be a fundamental principle in computer security. A static SoD (SSoD) policy states that in order to have all permissions necessary to complete a sensitive task, the cooperation of at least a certain number of users is required. Role-based access control (RBAC) is today's dominant access-control model. It is widely believed that one of RBAC's main strengths is that it enables the use of constraints to support policies, such as separation-of-duty. In the literature on RBAC, statically mutually exclusive roles (SMER) constraints are used to enforce SSoD policies. In this paper, we formulate and study fundamental computational problems related to the use of SMER constraints to enforce SSoD policies. We show that directly enforcing SSoD policies is intractable (coNP-complete), while checking whether an RBAC state satisfies a set of SMER constraints is efficient; however, verifying whether a given set of SMER constraints enforces an SSoD policy is also intractable (coNP-complete). We discuss the implications of these results. We show also how to generate SMER constraints that are as accurate as possible for enforcing an SSoD policy.
Multiplierless multiple constant multiplication
Authors: Voronenko Yevgen , Püschel Markus
Published: June 2007

A variable can be multiplied by a given set of fixed-point constants using a multiplier block that consists exclusively of additions, subtractions, and shifts. The generation of a multiplier block from the set of constants is known as the multiple constant multiplication (MCM) problem. Finding the optimal solution, namely, the one with the fewest number of additions and subtractions, is known to be NP-complete. We propose a new algorithm for the MCM problem, which produces solutions that require up to 20% less additions and subtractions than the best previously known algorithm. At the same time our algorithm, in contrast to the closest competing algorithm, is not limited by the constant bitwidths. We present our algorithm using a unifying formal framework for the best, graph-based MCM algorithms and provide a detailed runtime analysis and experimental evaluation. We show that our algorithm can handle problem sizes as large as 100 32-bit constants in a time acceptable for most applications. The implementation of the new algorithm is available at www.spiral.net.
Retroactive data structures
Authors: Demaine Erik D. , Iacono John , Langerman Stefan
Published: June 2007

We introduce a new data structuring paradigm in which operations can be performed on a data structure not only in the present, but also in the past. In this new paradigm, called
retroactive data structures
, the historical sequence of operations performed on the data structure is not fixed. The data structure allows arbitrary insertion and deletion of operations at arbitrary times, subject only to consistency requirements. We initiate the study of retroactive data structures by formally defining the model and its variants. We prove that, unlike persistence, efficient retroactivity is not always achievable. Thus, we present efficient retroactive data structures for queues, doubly ended queues, priority queues, union-find, and decomposable search structures.
Improved algorithms for weakly chordal graphs
Authors: Hayward Ryan B. , Spinrad Jeremy P. , Sritharan R.
Published: June 2007

We use a new structural theorem on the presence of two-pairs in weakly chordal graphs to develop improved algorithms. For the recognition problem, we reduce the time complexity from O(
mn
2
) to O(
m
2
) and the space complexity from O(
n
3
) to O(
m
+
n
), and also produce a hole or antihole if the input graph is not weakly chordal. For the optimization problems, the complexity of the clique and coloring problems is reduced from O(
mn
2
) to O(
n
3
) and the complexity of the independent set and clique cover problems is improved from O(
n
4
) to O(
mn
). The space complexity of our optimization algorithms is O(
m
+
n
).
A simple entropy-based algorithm for planar point location
Authors: Arya Sunil , Malamatos Theocharis , Mount David M.
Published: June 2007

Given a planar polygonal subdivision
S
, point location involves preprocessing this subdivision into a data structure so that given any query point
q
, the cell of the subdivision containing
q
can be determined efficiently. Suppose that for each cell
z
in the subdivision, the probability
p

z

that a query point lies within this cell is also given. The goal is to design the data structure to minimize the average search time. This problem has been considered before, but existing data structures are all quite complicated. It has long been known that the entropy
H
of the probability distribution is the dominant term in the lower bound on the average-case search time. In this article, we show that a very simple modification of a well-known randomized incremental algorithm can be applied to produce a data structure of expected linear size that can answer point-location queries in
O
(
H
) average time. We also present empirical evidence for the practical efficiency of this approach.
An exploratory study on the roles of network structure and knowledge processing orientation in work unit knowledge management
Authors: Song Seokwoo , Nerur Sridhar , Teng James T.C.
Published: June 2007

Knowledge management (KM), which concerns itself with the creation, storage, access and dissemination of intellectual assets, has been a dominant research theme in recent years. However, given the fact that organizational units differ in the way they process their knowledge, there is a need to understand how informational benefits that a unit within the organization accrues by virtue of its relationships with others in the network impact its creativity and KM effectiveness. In this study, we explore the potential contribution of network characteristics to both the creativity and overall KM effectiveness of intra-organizational units. In attempting to reaffirm and extend previous study findings, we accomplish our initial research objective by relating network characteristics to innovative outcomes with a more complete set of network centrality measures. In addition, the study demonstrates that when there is a fit between network structure and knowledge processing orientation, the effectiveness of perceived KM in the units will improve. Our results suggest that fostering an organizational climate that is conducive to extensive interaction and communication between units is likely to make the units more innovative throughout the organization
The influence of software intangibility on computer science and software engineering education
Authors: Hazzan Orit
Published: June 2007

In this short essay I will discuss how the fact that software is an intangible object influences Computer Science (CS) and Software Engineering (SE) education. Based on several observations that result from this analysis (Part A), I will then highlight the importance of teaching soft ideas in the framework of CS and SE education (Part B).
The MCDC paradox
Authors: Bhansali P. V.
Published: June 2007

Modified Condition/Decision Coverage (MCDC) is a structural testing strategy required to verify Level A software used in commercial aviation. In DO-178B, Level A software is defined as software whose anomalous behavior would cause or contribute to a failure of system function resulting in a catastrophic failure condition for the aircraft. Paradoxically, this technique does not detect common errors, yet it consumes a large portion (approximately 25%) of the verification budget because of the number of test cases required to satisfy this coverage. Furthermore, this approach is directly applicable to only high-level languages, making its applicability of limited value to assembly language programs and machine-level code which could have been generated by auto code tools. A simpler approach is suggested in this paper that would better detect these common errors and would be more cost-effective for all applications.
Validating modified cognitive complexity measure
Authors: Misra Sanjay
Published: June 2007

A newly proposed complexity measure is acceptable, only when its usefulness has been proved by a validation process. In our previous work, we proposed Modified Cognitive Complexity Measure (MCCM). In this paper, MCCM has been evaluated and validated through a practical framework and principle of measurement theory. It has been found to satisfy most of the parameters required by the practical framework and measurement theory. Additionally, empirical validation through case study and comparative study proved the robustness of the proposed measure.
Function level parallelism driven by data dependencies
Authors: Rul Sean , Vandierendonck Hans , De Bosschere Koen
Published: June 2007

With the rise of Chip multiprocessors (CMPs), the amount of parallel computing power will increase significantly in the near future. However, most programs are sequential in nature and have not been explicitly parallelized, so they cannot exploit these parallel resources. Automatic parallelization of sequential, non-regular codes is very hard, as illustrated by the lack of solutions after more than 30 years of research on the topic. The question remains if there is parallelism in sequential programs that can be detected automatically and if so, how much parallelism there is.

In this paper, we propose a framework for extracting potential parallelism from programs. Applying this framework to sequential programs can teach us how much parallelism is present in a program, but also tells us what the most appropriate parallel construct for a program is, e.g. a pipeline, master/slave work distribution, etc.

Our framework is profile-based, implying that it is not safe. It builds two new graph representations of the profile-data: the interprocedural data flow graph and the data sharing graph. This graphs show the data-flow between functions and the data structures facilitating this data-flow, respectively.

We apply our framework on the SPECcpu2000 bzip2 benchmark, achieving a speedup of 3.74 of the compression part and a global speedup of 2.45 on a quad processor system.
SPEC CPU2006 memory footprint
Authors: Henning John L.
Published: June 2007

The nominal goal for memory consumption by SPEC CPU2006 benchmarks is up to about 900 MB when compiled with 32-bit pointers. The 900 MB maxium was chosen so that a system with 1GB will have about 100MB available for the operating system and overhead processes. By comparison, the goal for SPEC CPU2000 was 200MB [1].
Performance counters and development of SPEC CPU2006
Authors: Henning John L.
Published: June 2007

Performance counters provide the means to track detailed events that occur on a CPU chip. These events are of interest to both performance analysts and compiler developers. Counting them provides essential clues to guide performance improvement. For example, a tester who sees that a program has a high cache miss rate on a particular system may experiment with compilation options that improve prefetching. A compiler developer who sees the same thing may realize that the code generator's machine model is missing some crucial detail of behavior on that particular system.
Internet nuggets
Authors: Thorson Mark
Published: June 2007

This column consists of selected traffic from the
comp.arch
newsgroup, a forum for discussion of computer architecture on the Internet---an international computer network.
Algorithmic approaches to symbolic integration and simplification
Authors: Collins G. E.
Published: June 2007

This panel session followed the format announced by SIGSAM Chairman Carl Engelman in the announcement published in SIGSAM Bulletin No. 10 (October 1968). Carl gave a brief (five or ten minutes) introduction to the subject and introduced Professor Joel Moses (M. I. T.). Joel presented an excellent exposition of the recent research accomplishments of the other panel members, synthesizing their work into a single large comprehensible picture. His presentation was greatly enhanced by a series of 27 carefully prepared slides containing critical examples and basic formulas, and was certainly the feature of the show. A panel discussion followed, with some audience participation. Panel members were Dr. W. S. Brown (Bell Telephone Laboratories), Professor B. F. Caviness (Duke University), Dr. Daniel Richardson and Dr. R. H. Risch (IBM).
A smaller FORTRAN-FORMAC system
Authors: Bahr K.
Published: June 2007

We have available a modified 7090-FORTRAN-FORMAC system and would like to offer this system to everybody who is still using the 7090/94. We know about PL/I-FORMAC and we use it, but we still have several programs which we don't want to rewrite and which run absolutely satisfactorily with our FORTRAN-FORMAC.
On dynamically-scoped crosscutting mechanisms
Authors: Tanter Éric
Published: June 2007

Many crosscutting mechanisms proposed in the literature offer means to restrain aspects to some dynamically-defined scopes. Dynamically-scoped mechanisms are particularly interesting because of the flexibility, expressiveness, and control they give over structural and behavioral changes made by aspects. Since the nature of dynamic scopes as well as the scoping mechanisms themselves greatly vary among proposals, It is relatively complex to compare them. This paper aims at filling this gap by proposing a first characterization of dynamically-scoped crosscutting mechanisms, hence providing a reference frame for comparing different approaches. As a result, this work clarifies some differences between related approaches, suggests possible tracks for further exploration of the design space of such mechanisms, and discusses some issues raised by dynamically-scoped aspects.
Using common off-the-shelf tools to implement dynamic aspects
Authors: Mahoney William R. , Sousan William L.
Published: June 2007

An emerging software engineering paradigm, Aspect-Oriented Programming, can be used to facilitate moving common interests or requirements from individual software functions into a separate module. Aspect code is woven into the software on either a static (compilation) basis or dynamic (runtime) basis. Existing systems necessitate the use of syntactic sugar. which is added to programs to indicate the join points in the software where aspects could potentially be applied. Static weaving inserts code, at compilation time, into these join points, while dynamic weaving might compile in code which can be activated at runtime.

This paper describes a new approach to the implementation of dynamic aspects in C/C++. Our method uses a tool which operates using the GCC compiler suite on Linux; it is a runtime event monitoring system we call "dynamicHook". The tool tests each potential join point at run time for the required activation of advice. If advice code is necessary at the join point it is loaded on the fly from shared libraries, retained for future use, and called dynamically.

No additions or modifications to the source code need to be made other than recompiling and linking in our library. The tool is thus targeted at adding aspect oriented methodologies to existing C/C++ code. We have demonstrated the tool by obtaining open-source web servers and adding dynamic aspects dealing with security and intrusion detection.
DNS Complexity
Authors: Vixie Paul
Published: June 2007

DNS is a distributed, coherent, reliable, autonomous, hierarchical database, the first and only one of its kind. Created in the 1980s when the Internet was still young but overrunning its original system for translating host names into IP addresses, DNS is one of the foundation technologies that made the worldwide Internet possible. Yet this did not all happen smoothly, and DNS technology has been periodically refreshed and refined. Though it’s still possible to describe DNS in simple terms, the underlying details are by now quite sublime. This article explores the supposed and true definitions of DNS and shows some of the tension between these two definitions through the lens of the Internet protocol development philosophy.
Beyond Beowulf Clusters
Authors: Papadopoulos Philip , Bruno Greg , Katz Mason
Published: June 2007

In the early ’90s, the Berkeley NOW Project under David Culler posited that groups of less capable machines could be used to solve scientific and other computing problems at a fraction of the cost of larger computers. In 1994, Donald Becker and Thomas Sterling worked to drive the costs even lower by adopting the then-fledgling Linux operating system to build Beowulf clusters at NASA’s Goddard Space Flight Center. By tying desktop machines together with open source tools such as PVM, MPI, and PBS, early clusters—which were often PC towers stacked on metal shelves with a nest of wires interconnecting them—fundamentally altered the balance of scientific computing. Before these first clusters appeared, distributed/parallel computing was prevalent at only a few computing centers, national laboratories, and a very few university departments. Since the introduction of clusters, distributed computing is now, literally, everywhere.
Review of "Embedded Linux Primer: A Practical Real-world Approach by Christopher Hallinan," Prentice Hall PTR, 2006, $44.99, ISBN: 0131679848.
Authors: State Radu
Published: June 2007

Review of "Embedded Linux Primer: A Practical Real-world Approach by Christopher Hallinan," Prentice Hall PTR, 2006, $44.99, ISBN: 0131679848.
Scheduling network traffic
Authors: Bonald Thomas , Roberts James
Published: June 2007

We discuss the potential of packet scheduling as a means to control traffic and improve performance for both wired and wireless links. Using simple queuing models that take into account the random nature of traffic, we draw practical conclusions about the expected gains and limits of scheduling.
Stochastic analysis of multiserver systems
Authors: Squillante Mark S.
Published: June 2007

This paper presents an overview of research in the stochastic analysis of multiserver systems, where scheduling often play a critical role. Our primary focus is on the stochastic analysis and optimization of multiserver systems in general, since most of this research directly investigates scheduling issues and all of this research provides the methods and results that have been and will continue to be used to study existing and future multiserver scheduling issues.
Correction on "Dynamic Polymorphism in Fortran 95" from August 2006 issue
Authors: Bader Reinhold
Published: June 2007

This authors' August 2006 article contained a discussion on the use of submodules to improve encapsulation for a dynamic polymorphism emulation which is incorrect.
Systems work at Microsoft Research
Authors: Schroeder Michael D.
Published: June 2007

Operating Systems Review
presents a special issue on systems work at Microsoft Research. This introduction sets the context for the papers.
BitVault
Authors: Zhang Zheng , Lian Qiao , Lin Shiding , Chen Wei , Chen Yu , Jin Chao
Published: June 2007

This paper summarizes our experience designing and implementing BitVault: a content-addressable retention platform for large volumes of reference data -- seldom-changing information that needs to be retained for a long time. BitVault uses "smart bricks" as the building block to lower the hardware cost. The challenges are to keep management costs low in a system that scales from one brick to tens of thousands, to ensure reliability, and to deliver a simple design. Our design incorporates peer-to-peer (P2P) technologies for self-managing and self-healing and uses massively parallel repair to reduce system vulnerability to data loss. The simplicity of the architecture relies on an eventually reliable membership service provided by a perfect one-hop distributed hash table (DHT). Its object-driven repair model yields last-replica recall guarantee independent of the failure scenario. So long as the last copy of a data object remains in the system, that data can be retrieved and its replication degree can be restored. A prototype has been implemented. Theoretical analysis, simulations and experiments have been conducted to validate the design of BitVault.
Singularity
Authors: Hunt Galen C. , Larus James R.
Published: June 2007

Every operating system embodies a collection of design decisions. Many of the decisions behind today's most popular operating systems have remained unchanged, even as hardware and software have evolved. Operating systems form the foundation of almost every software stack, so inadequacies in present systems have a pervasive impact. This paper describes the efforts of the Singularity project to re-examine these design choices in light of advances in programming languages and verification tools. Singularity systems incorporate three key architectural features: software-isolated processes for protection of programs and system services, contract-based channels for communication, and manifest-based programs for verification of system properties. We describe this foundation in detail and sketch the ongoing research in experimental systems that build upon it.
MapCruncher
Authors: Elson Jeremy , Howell Jon , Douceur John R.
Published: June 2007

Current large-scale interactive web mapping services such as Virtual Earth and Google Maps use large distributed systems for delivering data. However, creation and editorial control of their content is still largely centralized. The Composable Virtual Earth project's goal is to allow seamless interoperability of geographic data from arbitrary, distributed sources.

MapCruncher is a first step in this direction. It lets users easily create new interactive map data that can be layered on top of existing imagery such as road maps and aerial photography. MapCruncher geographically registers and reprojects the user's map into a standard coordinate system. It then emits metadata that makes it easy for anyone on the Internet to find the published map data and import it. Interactive maps them become distributed, seamlessly composable building blocks -- similar to images in the early days of the Web.
A design for high-performance flash disks
Authors: Birrell Andrew , Isard Michael , Thacker Chuck , Wobber Ted
Published: June 2007

Most commodity flash disks exhibit very poor performance when presented with writes that are not sequentially ordered. We argue that performance can be significantly improved through the addition of sufficient RAM to hold data structures describing a fine-grain mapping between disk logical blocks and physical flash addresses. We present a design that accomplishes this.
Teaching hands-on Linux host computer security
Authors: Shumba Rose
Published: June 2007

In the summer of 2003, a project to augment and improve the teaching of information assurance courses was started at IUP. Thus far, ten hands-on exercises have been developed. The exercises described in this article, and presented in the appendix, are based on actions required to secure a Linux host. Publicly available resources were used to develop the exercises, which have been successfully utilized since spring 2003 to teach cybersecurity basics classes. The experiences and challenges encountered in teaching the course and possible future work are also described.
Smart business networks
Authors: Heck Eric van , Vervest Peter
Published: June 2007

Realizing scenarios in which business is conducted through a rapidly formed network with anyone, anywhere, anytime regardless of different computer systems and business processes.
Cutting checks
Authors: Cotteleer Mark J. , Cotteleer Christopher A. , Prochnow Andrew
Published: June 2007

Open network e-payment systems are the future of corporate payments, assuming they address the challenges of integration, security, and remittance standards.
An empirical investigation of the effectiveness of systems modeling and verification tools
Authors: Jeyaraj Anand , Sauter Vicki L.
Published: June 2007

One reason system failure rates are not deterred by the latest best practices and tools may lie in how needs are (mis)interpreted by designers and users.
Time to rethink health care and ICT?
Authors: Avison David , Young Terry
Published: June 2007

Success for a new U.K. national health care system depends on clinical context and scale, along with the capacity to emphasize interpersonal communication.
Software patents and the metaphysics of Section 271(f)
Authors: Samuelson Pamela
Published: June 2007

Can shipment of one disk of software abroad give rise to worldwide liability for patent infringement? Is the Supreme Court ready to revisit the patentability of software?
Axioms for time dependence of resource consumption in computing recursive functions
Authors: Longo Giuseppe
Published: June 2007

Any formal definition of effective computability includes the idea of graduality of computation: whether it is a matter of Markov's algorithms (ANM) or of Turing Machines (TM) or of any other equivalent mathematical system, the elaboration progresses by discrete and successive instants.