bluuebunny/crossref_metadata_2025 huggingface dataset:
A critical-path-aware partial gating approach for test power reduction
Authors: Elshoukry Mohammed , Tehranipoor Mohammad , Ravikumar C. P.
Published: June 2007

Power reduction during test application is important from the viewpoint of chip reliability and for obtaining correct test results. One of the ways to reduce scan test power is to block transitions propagating from the outputs of scan cells through combinational logic. In order to accomplish this, some researchers have proposed setting primary inputs to appropriate values or adding extra gates at the outputs of scan cells. In this article, we point out the limitations of suchfull gatingtechniques in terms of area overhead and performance degradation. We propose an alternate solution where a partial set of scan cells is gated. A subset of scan cells is selected to give maximum reduction in test power within a given area constraint. An alternate formulation of the problem is to treat maximum permitted test power as a constraint and achieve a test power that is within this limit using the fewest number of gated scan cells, thereby leading to the least impact in area overhead. Our problem formulation also comprehends performance constraints and prevents the inclusion of gating points on critical paths. The area overhead is predictable and closely corresponds to the average power reduction.
Clustering and searching WWW images using link and page layout analysis
Authors: He Xiaofei , Cai Deng , Wen Ji-Rong , Ma Wei-Ying , Zhang Hong-Jiang
Published: June 2007

Due to the rapid growth of the number of digital images on the Web, there is an increasing demand for an effective and efficient method for organizing and retrieving the available images. This article describes iFind, a system for clustering and searching WWW images. By using a vision-based page segmentation algorithm, a Web page is partitioned into blocks, and the textual and link information of an image can be accurately extracted from the block containing that image. The textual information is used for image indexing. By extracting the page-to-block, block-to-image, block-to-page relationships through link structure and page layout analysis, we construct an image graph. Our method is less sensitive to noisy links than previous methods like PageRank, HITS, and PicASHOW, and hence the image graph can better reflect the semantic relationship between images. Using the notion of Markov Chain, we can compute the limiting probability distributions of the images, ImageRanks, which characterize the importance of the images. The ImageRanks are combined with the relevance scores to produce the final ranking for image search. With the graph models, we can also use techniques from spectral graph theory for image clustering and embedding, or 2-D visualization. Some experimental results on 11.6 million images downloaded from the Web are provided in the article.
Ubiquitous device personalization and use
Authors: Shacham Ron , Schulzrinne Henning , Thakolsri Srisakul , Kellerer Wolfgang
Published: June 2007

Service usage in emerging ubiquitous environments includes seamless and personalized usage of public and private devices discovered in the vicinity of a user. In our work, we describe an architecture for device discovery, device configuration, and the transfer of active sessions between devices. The presented architecture uses the Session Initiation Protocol (SIP) as a standardized, widely used signaling protocol for IP-based multimedia services. Our solution includes support of simple existing devices, split of sessions between devices, user-control of location-based behavior, and handling of security and privacy concerns. We present the implementation and show the feasibility of our work with analytical evaluation and measurements.
Transition predicate abstraction and fair termination
Authors: Podelski Andreas , Rybalchenko Andrey
Published: June 2007

Predicate abstraction is the basis of many program verification tools. Until now, the only known way to overcome the inherent limitation of predicate abstraction to safety properties was to manually annotate the finite-state abstraction of a program. We extend predicate abstraction to
transition predicate
abstraction. Transition predicate abstraction goes beyond the idea of finite
abstract-state
programs (and checking the absence of loops). Instead, our abstraction algorithm transforms a program into a finite
abstract-transition
program. Then a second algorithm checks fair termination. The two algorithms together yield an automated method for the verification of liveness properties under full fairness assumptions (impartiality, justice, and compassion). In summary, we exhibit principles that extend the applicability of predicate abstraction-based program verification to the full set of temporal properties.
The Pyramid Method
Authors: Nenkova Ani , Passonneau Rebecca , McKeown Kathleen
Published: June 2007

Human variation in content selection in summarization has given rise to some fundamental research questions: How can one incorporate the observed variation in suitable evaluation measures? How can such measures reflect the fact that summaries conveying different content can be equally good and informative? In this article, we address these very questions by proposing a method for analysis of multiple human abstracts into semantic content units. Such analysis allows us not only to quantify human variation in content selection, but also to assign empirical importance weight to different content units. It serves as the basis for an evaluation method, the Pyramid Method, that incorporates the observed variation and is predictive of different equally informative summaries. We discuss the reliability of content unit annotation, the properties of Pyramid scores, and their correlation with other evaluation methods.
Chinese semantic dependency analysis
Authors: Yan Jiajun , Bracewell David B. , Kuroiwa Shingo , Ren Fuji
Published: June 2007

Semantic analysis is a standard tool in the Natural Language Processing (NLP) toolbox with widespread applications. In this article, we look at tagging part of the Penn Chinese Treebank with semantic dependency. Then we take this tagged data to train a maximum entropy classifier to label the semantic relations between headwords and dependents to perform semantic analysis on Chinese sentences. The classifier was able to achieve an accuracy of over 84%. We then analyze the errors in classification to determine the problems and possible solutions for this type of semantic analysis.
Secure sessions for Web services
Authors: Bhargavan Karthikeyan , Corin Ricardo , Fournet Cédric , Gordon Andrew D.
Published: June 2007

We address the problem of securing sequences of SOAP messages exchanged between web services and their clients. The WS-Security standard defines basic mechanisms to secure SOAP traffic, one message at a time. For typical web services, however, using WS-Security independently for each message is rather inefficient; moreover, it is often important to secure the integrity of a whole session, as well as each message. To these ends, recent specifications provide further SOAP-level mechanisms. WS-SecureConversation defines
security contexts
, which can be used to secure sessions between two parties. WS-Trust specifies how security contexts are issued and obtained. We develop a semantics for the main mechanisms of WS-Trust and WS-SecureConversation, expressed as a library for TulaFale, a formal scripting language for security protocols. We model typical protocols relying on these mechanisms and automatically prove their main security properties. We also informally discuss some pitfalls and limitations of these specifications.
XQueC
Authors: Arion Andrei , Bonifati Angela , Manolescu Ioana , Pugliese Andrea
Published: June 2007

XML compression has gained prominence recently because it counters the disadvantage of the verbose representation XML gives to data. In many applications, such as data exchange and data archiving, entirely compressing and decompressing a document is acceptable. In other applications, where queries must be run over compressed documents, compression may not be beneficial since the performance penalty in running the query processor over compressed data outweighs the data compression benefits. While balancing the interests of compression and query processing has received significant attention in the domain of relational databases, these results do not immediately translate to XML data.

In this article, we address the problem of embedding compression into XML databases without degrading query performance. Since the setting is rather different from relational databases, the choice of compression granularity and compression algorithms must be revisited. Query execution in the compressed domain must also be rethought in the framework of XML query processing due to the richer structure of XML data. Indeed, a proper storage design for the compressed data plays a crucial role here.

The
XQ
ue
C
system (
XQ
uery Processor and
C
ompressor) covers a wide set of XQuery queries in the compressed domain and relies on a workload-based cost model to perform the choices of the compression granules and of their corresponding compression algorithms. As a consequence, XQueC provides efficient query processing on compressed XML data. An extensive experimental assessment is presented, showing the effectiveness of the cost model, the compression ratios, and the query execution times.
Computer science in a liberal arts context
Authors: Tenenberg Josh , McCartney Robert
Published: June 2007

This issue is devoted to the curriculum guidelines from the Liberal Arts Computer Science Consortium. These guidelines provide a coherent and important model for computing education within a liberal arts context, giving primacy to critical reason, rigorous methods, and student engagement in the research process. In this regard, they are at the same time both conservative, by giving low priority to the latest technologies, and radical by resisting the managerial impulse that at its worst commidifies and devalues higher education.
Deterministic sampling and range counting in geometric data streams
Authors: Bagchi Amitabha , Chaudhary Amitabh , Eppstein David , Goodrich Michael T.
Published: June 2007

We present memory-efficient deterministic algorithms for constructing ϵ-nets and ϵ-approximations of streams of geometric data. Unlike probabilistic approaches, these deterministic samples provide guaranteed bounds on their approximation factors. We show how our deterministic samples can be used to answer approximate online iceberg geometric queries on data streams. We use these techniques to approximate several robust statistics of geometric data streams, including Tukey depth, simplicial depth, regression depth, the Thiel-Sen estimator, and the least median of squares. Our algorithms use only a polylogarithmic amount of memory, provided the desired approximation factors are at least inverse-polylogarithmic. We also include a lower bound for noniceberg geometric queries.
An algorithm for deciding zero equivalence of nested polynomially recurrent sequences
Authors: Kauers Manuel
Published: June 2007

We introduce the class of nested polynomially recurrent sequences which includes a large number of sequences that are of combinatorial interest. We present an algorithm for deciding zero equivalence of these sequences, thereby providing a new algorithm for proving identities among combinatorial sequences: In order to prove an identity, decide by the algorithm whether the difference of lefthand-side and righthand-side is identically zero. This algorithm is able to treat mathematical objects which are not covered by any other known symbolic method for proving combinatorial identities. Despite its theoretical flavor and high complexity, an implementation of the algorithm can be successfully applied to nontrivial examples.
Dynamic text and static pattern matching
Authors: Amir Amihood , Landau Gad M. , Lewenstein Moshe , Sokol Dina
Published: June 2007

In this article, we address a new version of dynamic pattern matching. The
dynamic text and static pattern matching problem
is the problem of finding a static pattern in a text that is continuously being updated. The goal is to report all new occurrences of the pattern in the text after each text update. We present an algorithm for solving the problem where the text update operation is
changing
the symbol value of a text location. Given a text of length
n
and a pattern of length
m
, our algorithm preprocesses the text in time
O
(
n
log log
m
), and the pattern in time
O
(
m
log
m
). The extra space used is
O
(
n
+
m
log
m
). Following each text update, the algorithm deletes all prior occurrences of the pattern that no longer match, and reports all new occurrences of the pattern in the text in
O
(log log
m
) time. We note that the complexity is not proportional to the number of pattern occurrences, since all new occurrences can be reported in a succinct form.
Compressed representations of sequences and full-text indexes
Authors: Ferragina Paolo , Manzini Giovanni , Mäkinen Veli , Navarro Gonzalo
Published: June 2007

Given a sequence
S
=
s
1
s
2
…
s

n

of integers smaller than
r
=
O
(polylog(
n
)), we show how
S
can be represented using
nH
0
(
S
) +
o
(
n
) bits, so that we can know any
s

q

, as well as answer
rank
and
select
queries on
S
, in constant time.
H
0
(
S
) is the zero-order empirical entropy of
S
and
nH
0
(
S
) provides an information-theoretic lower bound to the bit storage of any sequence
S
via a fixed encoding of its symbols. This extends previous results on binary sequences, and improves previous results on general sequences where those queries are answered in
O
(log
r
) time. For larger
r
, we can still represent
S
in
nH
0
(
S
) +
o
(
n
log
r
) bits and answer queries in
O
(log
r
/log log
n
) time.

Another contribution of this article is to show how to combine our compressed representation of integer sequences with a compression boosting technique to design
compressed full-text indexes
that scale well with the size of the input alphabet Σ. Specifically, we design a variant of the FM-index that indexes a string
T
[1,
n
] within
nH

k

(
T
) +
o
(
n
) bits of storage, where
H

k

(
T
) is the
k
th-order empirical entropy of
T
. This space bound holds simultaneously for all
k
≤ α log
|Σ|
n
, constant 0 < α < 1, and |Σ| =
O
(polylog(
n
)). This index counts the occurrences of an arbitrary pattern
P
[1,
p
] as a substring of
T
in
O
(
p
) time; it locates each pattern occurrence in
O
(log
1+ε
n
) time for any constant 0 < ε < 1; and reports a text substring of length ℓ in
O
(ℓ + log
1+ε
n
) time.

Compared to all previous works, our index is the first that removes the alphabet-size dependance from all query times, in particular, counting time is linear in the pattern length. Still, our index uses essentially the same space of the
k
th-order entropy of the text
T
, which is the best space obtained in previous work. We can also handle larger alphabets of size |Σ| =
O
(
n
β
), for any 0 < β < 1, by paying
o
(
n
log|Σ|) extra space and multiplying all query times by
O
(log |Σ|/log log
n
).
The relative worst order ratio for online algorithms
Authors: Boyar Joan , Favrholdt Lene M.
Published: June 2007

We define a new measure for the quality of online algorithms, the
relative worst order ratio
, using ideas from the max/max ratio [Ben-David and Borodin 1994] and from the random order ratio [Kenyon 1996]. The new ratio is used to compare online algorithms directly by taking the ratio of their performances on their respective worst permutations of a worst-case sequence.

Two variants of the bin packing problem are considered: the classical bin packing problem, where the goal is to fit all items in as few bins as possible, and the dual bin packing problem, which is the problem of maximizing the number of items packed in a fixed number of bins. Several known algorithms are compared using this new measure, and a new, simple variant of first-fit is proposed for dual bin packing.

Many of our results are consistent with those previously obtained with the competitive ratio or the competitive ratio on accommodating sequences, but new separations and easier proofs are found.
From the chair
Authors: Sipior Janice C. , Lending Diane , Amoroso Donald L. , Shayo Conrad , Vowels Susan A.
Published: June 2007

I am happy to report that the ACM-SIGMIS CPR (Computer Personnel Research) 2007 Conference was a great success!

This year's conference was held at the Hyatt Regency Hotel in Saint Louis, Missouri, USA from April 19-21, 2007, http://www.sigmis.org/conferences.html. The theme was "The Global Information Technology Workforce." Please check the ACM Digital Library at: http://portal.acm.org/dl.cfm to find the SIGMIS CPR 2007 Conference Proceedings.

Thanks to the members of the 2007 CPR Conference Committee for all their efforts in making this conference a success:

Conference Co-Chairs:
Fred Niederman,
St. Louis University
Mary Sumner,
Southern Illinois University Edwardsville

Program Co-Chairs:
Diane Lending,
James Madison University
Chelley Vician,
Michigan Tech University

Local Arrangements:
Jo Ellen Moore,
Southern Illinois University Edwardsville
Susan Yager,
Southern Illinois University Edwardsville

Treasurer:
Donald Amoroso,
Appalachian State University

Publicity:
Anne Powell,
Southern Illinois University Edwardsville
Sandra Newton,
University of South Florida

Doctoral Consortium Co-Chairs:
Thomas W. Ferratt,
University of Dayton
Mike Gallivan,
Georgia State University

Please join me in congratulating the recipients of the fourth annual "Magid Igbaria Outstanding Conference Paper of the Year Award:" Tim Klaus, Stephen Wingreen, and J. Ellis Blanton for their paper, "Examining User Resistance and Management Strategies in Enterprise System Implementations." Warm congratulations to all of you!

At the close of the conference, the fifth annual SIGMIS Business Meeting was held. Fred Niederman, St. Louis University, and Mary Sumner, Illinois University Edwardsville, CPR 2007 Conference Co-Chairs, presented a Preliminary Outcome Report for the conference. Donald Amoroso, Appalachian State University, who is the CPR 2008 Conference Chair, provided a Progress Report. Next year's CPR 2008 Conference will be held in the beautiful Blue Ridge Mountains from April 19--21 in Boone, NC USA. Please visit www.sigmis.org/2008_CPR_Call_for_Papers.pdf for more information

I encourage you to submit your research to the CPR 2008 Conference. Everyone is welcome! Please continue to submit your best work to Data Base.

As always, we thank you for your continued support of SIGMIS. Please feel free to contact any one of us with suggestions or ideas to improve SIGMIS. Have a great summer!
The perceptual evaluation of information systems using the construct of user satisfaction
Authors: Leclercq Aurèlie
Published: June 2007

This research work concerns the perceptual evaluation of the performance of information systems (IS) and more particularly, the construct of user satisfaction. Faced with the difficulty of obtaining objective measures for the success of IS, user satisfaction appeared as a substitutive measure of IS performance (DeLone & McLean, 1992). Some researchers have indeed shown that the evaluation of an IS could not happen without an analysis of the feelings and perceptions of individuals who make use of it. Consequently, the concept of satisfaction has been considered as a guarantee of the performance of an IS. Also it has become necessary to ponder the drivers of user satisfaction. The analysis of models and measurement tools for satisfaction as well as the adoption of a contingency perspective has allowed the description of principal dimensions that have a direct or less direct impact on user perceptions

The case study of a large French group, carried out through an interpretativist approach conducted by way of 41 semi-structured interviews, allowed the conceptualization of the problematique of perceptual evaluation of IS in a particular field study. This study led us to confirm the impact of certain factors (such as perceived usefulness, participation, the quality of relations with the IS Function and its resources and also the fit of IS with user needs). On the contrary, other dimensions regarded as fundamental do not receive any consideration or see their influence nuanced in the case studied (the properties of IS, the ease of use, the quality of information). Lastly, this study has allowed for the identification of the influence of certain contingency and contextual variables on user satisfaction and, above all, for the description of the importance of interactions between the IS Function and the users
A field study on organizational commitment, professional commitment and peer mentoring
Authors: Bryant Scott E. , Moshavi Dan , Nguyen Thang V.
Published: June 2007

This study investigates attitudes and citizenship behaviors of IS workers in the software industry by examining relationships among various facets of organizational commitment, professional commitment, and a particular organizational citizenship behavior (OCB) called peer mentoring. Results revealed that one facet of organizational commitment, affective commitment, was positively associated with peer mentoring, while a second facet, normative commitment, was negatively associated with peer mentoring. A third facet of organizational commitment, continuance commitment, had no significant relationship with peer mentoring while professional commitment was positively associated with peer mentoring. Our results also found a positive and significant interaction between professional commitment and affective commitment, and a negative and significant interaction between professional commitment and normative commitment in predicting OCBs, suggesting that managers of software professionals can foster OCBs by focusing on specific facets of commitment
A systematic review of software process tailoring
Authors: Pedreira Oscar , Piattini Mario , Luaces Miguel R. , Brisaboa Nieves R.
Published: June 2007

Although software process proposals appear continuously, it is difficult to fit any of them into a given company as they are. Thus, some kind of adaptation or tailoring is always necessary. The goal of software process tailoring is to adapt an "off-the-shelf" software process to meet the needs of a specific organization or project. Although process tailoring is a mandatory activity in most software process proposals, it is usually carried out by following an ad-hoc approach, and the amount of research done on this topic to date can be considered small. This paper presents a systematic review of software process tailoring, analyzing the existing approaches towards this activity, discussing the main issues related to the problem, and providing an up-to-date and complete framework in which to position new research activities.
Expectation, experiment and reflection on internet software evolution
Authors: Yu Ping , Ma Xiaoxing , Lu Jian
Published: June 2007

Dynamic evolution is a challenging requirement of software application systems running in the open, dynamic and uncertain Internet. In this paper, we investigate expectations of Internet software evolution and propose a dynamic software architecture oriented approach. Notably, architecture information is reified as explicit and manipulable entities to support a runtime architecture meta-model, which is causally connected to the system implementation and specification. Moreover, mobile agent technology is exploited to implement the built-in architecture meta-model, supervising all evolutionary behaviors during runtime. A prototype supporting platform named Artemis-ARC is implemented as an attempt to facilitate the development of dynamically evolvable application systems. Based on existing practice, some reflection on Internet software evolution is also illustrated.
HDTrans
Authors: Sridhar Swaroop , Shapiro Jonathan S. , Bungale Prashanth P.
Published: June 2007

Dynamic translation is a general purpose tool used for instrumenting programs at run time. Many current translators perform substantial rewriting during translation in an attempt to reduce execution time. When dynamic translation is used as a ubiquitous policy enforcement mechanism, the majority of program executions have no dominating inner loop that can be used to amortize the cost of translation. Even under more favorable usage assumptions, our measurements show that such optimizations offer no significant benefit in most cases. A simpler, more maintainable, adaptable, and smaller translator may be preferable to more complicated designs.

In this paper, we present HDTrans, a light-weight IA-32 to IA-32 binary translation system that uses some simple and effective translation techniques in combination with established trace linearization and code caching optimizations. We also present an evaluation of translation overhead under non-ideal conditions, showing that conventional benchmarks do not provide a good prediction of translation overhead when used pervasively.

A further contribution of this paper is an analysis of the effectiveness of post-compile static pre-translation techniques for overhead reduction. Our results indicate that static pre-translation is effective only when expensive instrumentation or optimization is performed, and that efficient reload of pre-translated code incurs a substantial execution-time penalty.
Introduction to the special issue on the 2006 workshop on design, analysis, and simulation of chip multiprocessors
Authors: Tullsen Dean , Kumar Rakesh , Jouppi Norman P.
Published: June 2007

Chip multiprocessor architectures are becoming increasingly attractive as an option to provide high instruction throughput while keeping power and complexity under control. Such architectures have also been shown to have scalability and productivity advantages. Multi-core processors are fast becoming mainstream.
A hardware/software framework for supporting transactional memory in a MPSoC environment
Authors: Ferri Cesare , Moreshet Tali , Bahar R. Iris , Benini Luca , Herlihy Maurice
Published: June 2007

Manufacturers are focusing on multiprocessor-system-on-a-chip (MPSoC) architectures in order to provide increased concurrency, rather than increased clock speed, for both large-scale as well as embedded systems. Traditionally lock-based synchronization is provided to support concurrency; however, managing locks can be very difficult and error prone. In addition, the performance and power cost of lock-based synchronization can be high. Transactional memories have been extensively investigated as an alternative to lock-based synchronization in general-purpose systems. It has been shown that transactional memory has advantages over locks in terms of ease of programming, performance and energy consumption. However, their applicability to embedded multi-core platforms has not been explored yet. In this paper, we demonstrate a complete hardware transactional memory solution for an embedded multi-core architecture, consisting of a cache-coherent ARM-based cluster, similar to ARM's MPCore. Using cycle accurate power and performance models for the transactional memory hardware, we evaluate our architectural framework over a set of different system and application settings, and show that transactional memory is a promising solution, even for resource-constrained embedded multiprocessors.
Guest editor's introduction
Authors: Henning John L.
Published: June 2007

During the development of the new benchmark suite CPU2006, SPEC analyzed benchmark candidates for various technical attributes, including time profiles, language standard compliance, I/O activity, system resource usage, and many other attributes. Many people contributed to the analysis, as shown in the credits at www.spec.org/cpu2006/docs/credits.html. This issue of Computer Architecture News presents a set of articles flowing from that analysis effort.
Subsetting the SPEC CPU2006 benchmark suite
Authors: Phansalkar Aashish , Joshi Ajay , John Lizy K.
Published: June 2007

On August 24, 2006, the Standard Performance Evaluation Corporation (SPEC) announced CPU2006 -- the next generation of industry-standardized CPU-intensive benchmark suite. The SPEC CPU benchmark suite has become the most frequently used suite for simulation-based computer architecture research. Detailed processor simulators take days to weeks to simulate each of the SPEC CPU programs. In order to reduce simulation to a tractable time, architects and researchers often use only a subset of benchmarks from the SPEC CPU suite to evaluate the potential of their ideas. Prior research has demonstrated that statistical techniques are most effective to find a representative subset of benchmark programs from a benchmark suite. The objective of this paper is to apply multivariate statistical data analysis techniques for selecting a representative subset of programs from the SPEC CPU2006 benchmark suite. We measure a set of performance counter based characteristics for the SPEC CPU2006 programs across a large number of architectures and apply multivariate statistical analysis techniques to find a representative subset of benchmarks and representative input sets wherever multiple input sets are provided. The results from this paper will help architects and researchers to find a smaller but representative set of programs from the SPEC CPU2006 benchmark suite, when time or resource constraints prohibit experimentation with the entire benchmark suite.
CPU2006 working set size
Authors: Gove Darryl
Published: June 2007

SPEC CPU2000 had a target memory footprint of 200 MB for the benchmarks [1], to enable the suite to run on machines with 256 MB of memory. Six years have elapsed since the release of that suite, and in that time memory sizes have increased significantly, so the memory requirements for the recently released CPU2006 reflect this. CPU2006 has been targeted to have a benchmark memory footprint of about 900MB, allowing the suite to run on machines with 1GB of memory.
Characterization of file I/O activity for SPEC CPU2006
Authors: Ye Dong , Ray Joydeep , Kaeli David
Published: June 2007

SPEC CPU2006 is a compute-intensive benchmark suite designed to stress a computer system's processor, memory subsystem, and compiler. To construct this suite, SPEC has selected benchmarks that are derived from real world applications. When run with their reference inputs, these programs place a significant computational burden on today's mainstream desktops as well as high-end workstations and servers.

For these applications to thoroughly exercise the merits of a particular processor/memory design point, it is necessary to limit the amount of I/O activity generated. Since these applications come from real world applications, the suite developers have considered how best to limit the amount of file-based I/O activity present in these applications. This paper presents the characteristics of file I/O activity in the resulting suite and its overall impact on the performance of these applications. We also report on some of the choices SPEC has made in order to reduce the file I/O activity in some specific programs of the suite.
Evaluating the correspondence between training and reference workloads in SPEC CPU2006
Authors: Gove Darryl , Spracklen Lawrence
Published: June 2007

Profile feedback (sometimes called Feedback Directed Optimisation FDO) is a useful technique for providing the compiler with additional information about runtime program flow. The compiler is able to use this information to make optimisation decisions that improve the way the code is laid out in memory or determine which routines are inlined, and hence improve the performance of the application.

The use of profile feedback requires the code to be compiled twice. The first time the compiler generates an instrumented version of the application. This instrumented version is then run on one or more 'representative' training workloads to gather profile data. This profile data contains information such as how many times each routine is executed and how frequently each branch is taken. The second pass through the compiler uses this information to make more enlighted optimisation decisions.

The quality of the training data impacts the ability of the compiler to do the best job that it can. This paper discusses a method of assessing the similarity of the training workload to the reference workload, and applies this methodology to evaluate the training workloads in the SPEC CPU2006 benchmark suite.
SPEC CPU2006 benchmark tools
Authors: Spradling Cloyce D.
Published: June 2007

The benchmarks that make up the SPEC CPU2006 benchmark suite are set-up, run, timed, and scored by the CPU tools harness. The tools have evolved over time from a collection of edit-it-yourself makefiles, scripts, and an Excel spreadsheet to the current Perl-based suite. The basic purpose of the tools is to make life easier for the benchmarker; they make it easier to tweak compilation settings, easier to keep track of those settings, and most importantly, they make it easier to follow the run and reporting rules.
From the SIGSAM subcommittee on computation of algebraic structures
Authors: Neubüser Joachim
Published: June 2007

So far, the following colleagues have agreed to act as members of the subcommittee:

John J. Cannon, Department of Pure Mathematics, The University of Sydney, Sydney, N.S.W. 2006, Australia.

(Programs for the investigation of groups, Lie rings, etc.; symbol manipulation languages.)

Stig Flodmark, Institutionen för Teoretisk Fysik, Stockholms Universitet, Vanadisvágen 9, Stockholm VA, Sweden.

(Programs for non-numerical mathematics for application in physics.)

John Mc Kay, Atlas Computer Laboratory, Chilton, Didcot, Berkshire, England.

(Programs for the investigation of groups.)

Robert J. Plemmons, Mathematics Department, The University of Tennessee, Knoxville, Tennessee 37916, USA.

(Programs for the investigation of semigroups and related structures.)
An unlikely HCI frontier
Authors: Pew Richard W.
Published: June 2007

This inaugurates a series of guest-authored Timelines columns. Richard Pew's research focus has been in human factors. He was the program chair for the first official CHI Conference in 1983 and participated on three panels at CHI'86. He was president of the Human Factors Society and the first chair of the National Research Council Committee on Human Factors. He wrote the HCI history chapter for the first edition of the Erlbaum Handbook of Human-Computer Interaction, edited by Julie Jacko and Andrew Sears. In this column he describes an innovative project in the dynamic late 1970s that brought Xerox PARC technology to a government bureaucracy.---Jonathan Grudin, Timelines editor
What makes UX successful from the executive perspective?
Authors: Desmond Kristin
Published: June 2007

Mark Vershel served as vice president and general manager for Borland, an application lifecycle management company. Mark oversaw user experience during the period when a number of groundbreaking products from a user interface perspective---exemplified by Turbo Pascal, Borland C++, Quattro Pro and Paradox---were introduced into the consumer and developer software markets.
Extending ACID semantics to the file system
Authors: Wright Charles P. , Spillane Richard , Sivathanu Gopalan , Zadok Erez
Published: June 2007

An organization's data is often its most valuable asset, but today's file systems provide few facilities to ensure its safety. Databases, on the other hand, have long provided transactions. Transactions are useful because they provide atomicity, consistency, isolation, and durability (ACID). Many applications could make use of these semantics, but databases have a wide variety of nonstandard interfaces. For example, applications like mail servers currently perform elaborate error handling to ensure atomicity and consistency, because it is easier than using a DBMS. A transaction-oriented programming model eliminates complex error-handling code because failed operations can simply be aborted without side effects. We have designed a file system that exports ACID transactions to user-level applications, while preserving the ubiquitous and convenient POSIX interface. In our prototype ACID file system, called Amino, updated applications can protect arbitrary sequences of system calls within a transaction. Unmodified applications operate without any changes, but each system call is transaction protected. We also built a recoverable memory library with support for nested transactions to allow applications to keep their in-memory data structures consistent with the file system. Our performance evaluation shows that ACID semantics can be added to applications with acceptable overheads. When Amino adds atomicity, consistency, and isolation functionality to an application, it performs close to Ext3. Amino achieves durability up to 46% faster than Ext3, thanks to improved locality.
Building MEMS-based storage systems for streaming media
Authors: Rangaswami Raju , Dimitrijević Zoran , Chang Edward , Schauser Klaus
Published: June 2007

The performance of streaming media servers has been limited by the dual requirements of high disk throughput (to service more clients simultaneously) and low memory use (to decrease system cost). To achieve high disk throughput, disk drives must be accessed with large IOs to amortize disk access overhead. Large IOs imply an increased requirement of expensive DRAM, and, consequently, greater overall system cost. MEMS-based storage, an emerging storage technology, is predicted to offer a price-performance point between those of DRAM and disk drives. In this study, we propose storage architectures that use the relatively inexpensive MEMS-based storage devices as an intermediate layer (between DRAM and disk drives) for temporarily staging large disk IOs at a significantly lower cost. We present data layout mechanisms and synchronized IO scheduling algorithms for the real-time storage and retrieval of streaming data within such an augmented storage system. Analytical evaluation suggests that MEMS-augmented storage hierarchies can reduce the cost and improve the throughput of streaming servers significantly.
Analysis and modeling of job arrivals in a production grid
Authors: Li Hui , Muskulus Michael
Published: June 2007

In this paper we present an initial analysis of job arrivals in a production data-intensive Grid and investigate several traffic models for the interarrival time processes. Our analysis focuses on the heavy-tail behavior and autocorrelations, and the modeling is carried out at three different levels:
Grid, Virtual Organization (VO)
, and
region
. A set of
m-state Markov modulated Poisson processes (MMPP)
is investigated, while
Poisson processes
and
hyperexponential renewal processes
are evaluated for comparison studies. We apply the
transportation distance
metric from dynamical systems theory to further characterize the differences between the data trace and the simulated time series, and estimate errors by
bootstrapping
. The experimental results show that MMPPs with a certain number of states are successful to a certain extent in simulating the job traffic at different levels, fitting both the interarrival time distribution and the autocorrelation function. However, MMPPs are not able to match the autocorrelations for certain VOs, in which strong deterministic semi-periodic patterns are observed. These patterns are further characterized using different representations. Future work is needed to model both deterministic and stochastic components in order to better capture the correlation structure in the series.
Fairness and classifications
Authors: Wierman Adam
Published: June 2007

The growing trend in computer systems towards using scheduling policies that prioritize jobs with small service requirements has resulted in a new focus on the fairness of such policies. In particular, researchers have been interested in whether prioritizing small job sizes results in large jobs being treated "unfairly." However, fairness is an amorphous concept and thus difficult to define and study. This article provides a short survey of recent work in this area.
Scheduling in practice
Authors: Biersack Ernst W. , Schroeder Bianca , Urvoy-Keller Guillaume
Published: June 2007

In queueing theory, it has been known for a long time that the scheduling policy used in a system greatly impacts user-perceived performance. For example, it has been proven in the 1960's that size-based scheduling policies that give priority to short jobs are optimal with respect to mean response time. Yet, virtually no systems today implement these policies. One reason is that real systems are significantly more complex than a theoretical M/M/1 or M/G/1 queue and it is not obvious how to implement some of these policies in practice. Another reason is that there is a fear that the big jobs will "starve", or be treated unfairly as compared to Processor-Sharing (PS). In this article we show, using two important real world applications, that size-based scheduling can be used in practice to greatly improve mean response times in real systems, without causing unfairness or starvation. The two applications we consider are connection scheduling in web servers and packet scheduling in network routers.
A perspective on computing research management
Authors: Levin Roy
Published: June 2007

This paper offers a perspective on a particular set of principles that have guided the development and enabled the success of several noteworthy corporate research labs in computer science. The paper examines the differences between the corporate computing research environment and academia, then describes the model for managing research that Microsoft Research employs, illustrating how it reflects those differences and what the consequences are.
Autopilot
Authors: Isard Michael
Published: June 2007

Microsoft is rapidly increasing the number of large-scale web services that it operates. Services such as Windows Live Search and Windows Live Mail operate from data centers that contain tens or hundreds of thousands of computers, and it is essential that these data centers function reliably with minimal human intervention. This paper describes the first version of
Autopilot
, the automatic data center management infrastructure developed within Microsoft over the last few years. Autopilot is responsible for automating software provisioning and deployment; system monitoring; and carrying out repair actions to deal with faulty software and hardware. A key assumption underlying Autopilot is that the services built on it must be designed to be manageable. We also therefore outline the best practices adopted by applications that run on Autopilot.
Teaching context in information security
Authors: Bishop Matt
Published: June 2007

This article investigates teaching the application of technical ideas by non-technical means, especially by using puzzles to engage students. After discussing the need to teach students to evaluate contexts in which decisions about computer security must be made, we suggest questions and scenarios drawn from political science, history, as well as other humanities, to force students to apply or derive principles of computer security in unusual and unexpected situations. Our experience shows that students find the process enjoyable, stimulating, and effective.
Ganzúa
Authors: García-Pasquel Jesús Adolfo , Galaviz José
Published: June 2007

Many introductory courses to cryptology and computer security start with or include a discussion of classical ciphers that usually contemplates some cryptanalysis techniques used to break them. Ganzúa (picklock in Spanish) is an application designed to assist the cryptanalysis of ciphertext obtained with monoalphabetic or polyalphabetic ciphers. It can use almost arbitrary character sets for the plain and cipher alphabets as well as obtain the standard relative frequencies of many languages and provide other useful data.
Evolution and emerging issues in mobile wireless networks
Authors: Dekleva Sasha , Shim J.P. , Varshney Upkar , Knoerzer Geoffrey
Published: June 2007

Assessing the widespread deployment and increasing use of mobile services.
Design patterns for managing product life cycle information
Authors: Främling Kary , Ala-Risku Timo , Kärkkäinen Mikko , Holmström Jan
Published: June 2007

Agent-based architectures, taking queues from object-oriented programming, can make product information accessible in controlled ways over the Net.
Perceived health risks of 3G cell phones
Authors: Cocosila Mihail , Turel Ofir , Archer Norm , Yuan Yufei
Published: June 2007

Studying the perception of health risks associated with mobile phones and the implications for usage.
The degree diagram of undecidable problems of formal grammars
Authors: Cudia Dennis F.
Published: June 2007

Let O be the degree of all solvable problems, let O' be the degree of unsolvability of the halting problem for Turing machines, let O'' be the degree of unsolvability of the problem of whether an arbitrary Turing machine eventually halts for only finitely many finite initial configurations, and let O''' be the degree of unsolvability of the problem of whether an arbitrary Turing machine never halts for only finitely many finite initial configurations. Let ≤ denote the partial ordering of Turing reducibility. Then using results and methods of 1. and 2., the following degree diagram refinement of a table of solvable and unsolvable problems, which appears in 3., p. 230, may be obtained.
Computational complexity and Gödel's incompleteness theorem
Authors: Chaitin G. J.
Published: June 2007

Given any simply consistent formal theory F of the state complexity L(S) of finite binary sequences S as computed by 3-tape-symbol Turing machines, there exists a natural number L(F) such that L(S) > n is provable in F only if n < L(F). On the other hand, almost all finite binary sequences S satisfy L(S) < L(F). The proof resembles Berry's paradox, not the Epimenides nor Richard paradoxes.
Taking the network on the road
Authors: Rosenberg Timothy , Hoffman Lance J.
Published: June 2007

Educational institutions that wish to implement a specialized teaching laboratory often have a variety of obstacles to overcome. Some of these obstacles are related to adapting existing classroom infrastructure, building the laboratory, and meeting the demands for multiple-use classrooms to maximize the return on investment. In some cases, such as computer security, they must also maintain a controlled environment. Portable educational networks of computers allow teaching specialized topics that have heretofore required specialized laboratories in existing classrooms. Their flexibility allows them to be used for a variety of content---operating systems, networking, security, and forensics. These systems are in use today supporting undergraduate, graduate, and professional education.
Dispelling 10 common disaster recovery myths
Authors: Landry Brett J. L. , Koger M. Scott
Published: June 2007

Disasters happen all the time; yet despite this, many organizations are caught unprepared or make unrealistic assumptions. These factors create environments that will fail during a disaster. Most information technology (IT) curricula do not cover disaster recovery (DR) plans and strategies in depth. The unfortunate result is that most new computer systems are implemented without sufficient disaster recovery plans and testing. Courses on network security need to examine DR as a real threat and cover it as a core module. By dispelling the 10 common myths, organizations can better plan, develop, and test true DR plans.