bluuebunny/crossref_metadata_2025 huggingface dataset:
Impact of libre software tools and methods in the robotics field
Authors: Barrera Pablo , Robles Gregorio , Cañas José M. , Martín Francisco , Matellán Vicente
Published: November 2005

Software is one of the major components of robots; in fact, it is the main bottleneck for the proliferation of robotics in our everyday lives. In the last years the field of robotics has been an emerging application area of the libre (free/open source) software phenomenon. Libre software tools have been traditionally popular among the robotics research and teaching community. Even companies whose main business model is to sell robots have found convenient to share the software in order to promote a community around their products. In this paper we analyze the situation of libre software in these three subareas: industry, teaching and research. In particular, we describe commercial robots like the Cye and the Pioneer, a software platform like Orocos as a examples of industrial world applications, the libre tools around the LEGO Mindstorms in the case of teaching, and the Robocup competition and the Player/Stage platform in research area. All these cases show that libre software can act as a catalyst in the robotics industry which is still a sector in its early research and industrial stages.
F/OSS in the library world
Authors: Chawner Brenda
Published: November 2005

Existing research into free/open source software development has largely ignored the nature of the application domain the software is for. Jørgensen and Sørensen's 'development arena' [12] provides a useful conceptual framework for grouping and comparing projects. This paper applies the framework to free/open source software projects in two library and information management application spaces: integrated library systems and institutional repositories. The preliminary analysis shows that F/OSS projects to develop integrated library systems are generally small scale, and the software is used mainly by smaller libraries. Institutional repository software, not widely available from commercial vendors, is being developed by larger libraries, often with the assistance of research funding from other bodies, and is being implemented by university and research libraries worldwide.
OSS tools in a heterogeneous environment for embedded systems modelling
Authors: Persson Anna , Gustavsson Henrik , Lings Brian , Lundell Björn , Mattsson Anders , Ärlig Ulf
Published: November 2005

The development and maintenance of UML models is an inherently distributed activity, where distribution may be geographical, temporal or both. It is therefore increasingly important to be able to interchange model information between tools - whether in a tool chain, for legacy reasons or because of the natural heterogeneity resulting from distributed development contexts. In this study we consider the current utility of XMI interchange for supporting OSS tool adoption to complement other tools in an embedded systems development context. We find that the current state of play is disappointing, and speculate that the problem lies both with the open standards and the way in which they are being supported and interpreted. There is a challenge here for the OSS community to take a lead as tool vendors gear up for XMI 2.0.
The advanced mobile application testing environment
Authors: Binder Robert V. , Hanlon James E.
Published: November 2005

The Advanced Mobile Application Testing Environment (AMATE) combines model-based test generation and evaluation, controllable RF airlink variation, and a robust standards-based distributed test harness for end-to-end testing of distributed mobile applications. This report summarizes AMATE capabilities.
Modeling for image processing system validation, verification and testing
Authors: Li Xing , Nagarajan Ramesh
Published: November 2005

State of the art digital copiers and multifunctional devices not only has millions of lines of software code but also employ application specific hardware components each having millions of gates to perform sophisticated image processing functions. To ensure high quality of the system, an image path system model, which contains both an image processing driver model part and a hardware component model part, is constructed. The modeling work not only facilitates system validation, verification and testing but also maximizes the reuse of well-tested artifacts. This paper describes the image path system model and its development process.
Using iDAVE to determine availability requirements
Authors: Huang LiGuo , Boehm Barry
Published: November 2005

Different systems have different success-critical stakeholders. Even for the same system, these stakeholders may depend on it in different ways for different scenarios. Therefore a one-size-fits-all dependability metric is unachievable in practice. In order to cost-effectively achieve the stakeholders' desired dependability attribute requirements for a given project, we have to solve such problems as how to define an appropriate level for a particular dependability attribute and how much dependability investment is enough for a particular software/scenario class. However, the answers to those questions are traditionally difficult to obtain. This paper uses a hypothetical Lunar Biological Laboratory (LBL) as an example to illustrate how to use the iDAVE model to determine the appropriate levels of availability requirements for different software/scenario classes based on their different ROI profiles.
Early estimation of software quality using in-process testing metrics
Authors: Nagappan Nachiappan , Williams Laurie , Vouk Mladen , Osborne Jason
Published: November 2005

In industrial practice, information on post-release field quality of a product tends to become available too late in the software development process to affordably guide corrective actions. An important step towards remediation of this problem of late information lies in the ability to provide an early estimation of software post-release field quality. This paper presents the use of a suite of in-process metrics that leverages the software testing effort to provide (1) an estimation of potential software field quality in early software development phases, and (2) the identification of low quality software programs. A controlled case study conducted at North Carolina State University provides initial indication that our approach is effective for making an early assessment of post-release field quality.
IMCE
Authors: Adams Brett , Venkatesh Svetha , Jain Ramesh
Published: November 2005

We discuss the design goals for an integrated media creation environment (IMCE) aimed at enabling the average user to create media artifacts with professional qualities. The resulting requirements are implemented and we demonstrate the efficacy of the resulting system with the generation of two simple home movies. The significance for the average user seeking to create home movies lies in the flexible and automatic application of film principles to the task, removal of tedious low-level editing by means of well-formed media transformations in terms of high-level film constructs (e.g., tempo), and content repurposing powered by those same transformations added to the rich semantic information maintained at each phase of the process.
Do we need ANY mathematics in computer science curricula?
Authors: Ralston Anthony
Published: November 2005

Do we need math in CS? Silly question, isn't it? Just look at all the computer science curricula ever proposed, most recently CC2001, the ACM-IEEE/CS effort [1]. Mathematics plays a significant role in all of them. So why even pose the question? Well, bear with me.
Preparing the STEM workforce of the 21
st
century
Authors: Martin C. Dianne
Published: November 2005

Just hot off the press is the final report of an NSF-funded workshop entitled, "Preparing the STEM Workforce of the 21
st
Century: Broadening Participation through a Comprehensive, Integrated System." This report summarizes discussions and recommendations resulting from a workshop convened last year at the National Science Foundation to examine issues surrounding the development of a diverse and well-prepared science and engineering workforce for the 21
st
century. STEM is the acronym for the major disciplines funded by NSF: Science (including the social sciences), Technology, Engineering, and Mathematics. The report is a worthwhile read for all CS educators concerned about increasing the diversity of the CS student population.
Reflections on standards
Authors: Williams Michael R.
Published: November 2005

Today we use our computers, add extra peripherals and install software without much thought as to whether they will work as advertised. When we are using a windows-style interface, even with an unfamiliar bit of software, we naturally expect to find the "save" command as part of the drop-down "file" menu and some form of help will always be available as the right-most menu item. A few years ago I was in China to give a conference presentation and had to help a fellow presenter set up a computer for his PowerPoint talk the next day. Our hosts had kindly provided us with a computer, but all the menus were in Chinese. It was only the fact that we knew where to look in the drop-down menus for the standard facilities that enabled us to (with only a slight problem) get his presentation ready for the next session.
Grand challenges
Authors: Lister Raymond
Published: November 2005

A recent paper in the (British) Computer Journal [1] described the "Grand Challenges" for Computing Education [1]. With student numbers falling worldwide, this certainly is a challenging period for our discipline. The paper is timely and worthwhile reading. It discusses several problems facing the discipline, but in a positive way, by attempting to identify the solutions to those problems. This column will concentrate on some of the problems/solutions from that paper that might be answered via education research.
Mathematics and CS topics in the CS classroom
Authors: Walker Henry M.
Published: November 2005

Tony Ralston and Peter Henderson have written columns for this issue discussing mathematics for computer science. This column considers possible implications for the classroom. While the ideas in this column are not particularly new, perhaps they will stimulate discussion.
Tuple enumeration
Authors: Ginat David
Published: November 2005

The editorial of this
inroads
issue elaborates on the need of mathematics in the CS curricula. Tony Ralston refers to both the general notion of math in CS and the particular courses of calculus and discrete mathematics. This column adds a related facet.
What is computer science?
Authors: Parlante Nick
Published: November 2005

I've been thinking about the meaning of the January "What is CS" thread on the SIGCSE email list. Like many of you, I got behind reading it, and in the back of my mind, I was afraid as I caught up that it might degenerate into that special hell demonstrated on so many newsgroup and Slashdot threads --- a "discussion" gradually dominated by the most polar, loud, and least self-disciplined contributors.
Using a faculty portfolio in the distinction of teaching
Authors: Samaka M.
Published: November 2005

In this paper a faculty portfolio in the computer science discipline is being designed and used in teaching summative evaluation. As an example model, the paper presents an academic portfolio that intends to contain the author's major achievements in teaching at a university level. The portfolio was submitted for the faculty distinction award in teaching at UAE University in United Arab Emirates. The structure of the portfolio was carefully designed according to a suggested evaluation criteria model concluded throughout an investigation study conducted by the author of this paper. The structure also meets the summative rating process for the faculty distinction award in teaching at UAE University.
Teach 2D graphics concepts with an OpenGL graphing program
Authors: Lorenzen Torben , Michaud Joseph
Published: November 2005

The authors present an OpenGL program that draws a sheet of interactive graph paper on the computer screen. Examples are given illustrating how the program is used to teach 2D concepts in the beginning of a graphics course. The students in this course also code the program over a five week period. The student assignments and the graphing program are available via internet download.
E-learning of trend modeling in a web-environment
Authors: Tegos Georgios K. , Stoyanova Diana V. , Onkov Kolyo Z.
Published: November 2005

A general scheme of the e-learning system for trend modeling is presented. Random Number Generator determines the length of time series extracted from the HTML-presented Fishery Time Series (FTS) database. The developed Web-environment combines computing and training components. The computing part covers the access to the database and the statistical computation procedures. The training part provides help and advice by the conducted dialogue between the student and the computer. Network resources are effectively shared to ensure fast communication between the server and the client computers. Programming techniques have been developed for the management of the training process.
Professional development workshop for female software engineers
Authors: Hazzan Orit
Published: November 2005

This article presents a perspective on the professional development of software engineers, with a focus on women in the field. Specifically, a professional development workshop for female software engineers is presented. The article starts by explaining the need for such a workshop. Then, the workshop purpose and objectives, workshop structure, workshop activities and a possible workshop format are presented.
The computer science debate
Authors: Lewis Tracy L. , Smith Wanda J.
Published: November 2005

This paper examines some of the ongoing identity challenges for the computer science community: definition, purpose, pedagogy, and curriculum drivers. This research contends that there are three primary social theories driving one's perspective of computer science: resource based theory, resource dependency theory, and social exchange theory. A conceptual framework is presented that examines the likely definition, purpose, pedagogy, and curriculum drivers for each perspective. The framework was evaluated in a qualitative study using the e-mails threads from a discussion on the SIGCSE listserv. The results of this study and the implications of future of computer science are discussed.
High school environments and girls' interest in computer science
Authors: Olivieri Lisa M.
Published: November 2005

This paper presents a brief literature review of the involvement of women in computer science, of high school computer science curricula, and of an increasing interest in single-sex education. A study was conducted to determine if the high school environment is a factor in encouraging girls' interest in and attitude toward computers. A description of the study and its results are discussed.
Community and accountability in a first year programming sequence
Authors: Howles Trudy
Published: November 2005

The paper documents the partial results of a multi-year study of first-year students enrolled in an introductory programming sequence. Key components of this project focus on transitioning the course from a lecture to a studio environment, the formation of a student cohort based on skill level and initiatives to encourage a higher level of student accountability and success.This paper focuses on the experiences in implementing the cohort, establishing a course support system for students and modifying the attendance policy. Also discussed are initiatives to improve accountability and build student confidence through collaborative learning and a sense of community.
Why the high attrition rate for computer science students
Authors: Beaubouef Theresa , Mason John
Published: November 2005

This paper investigates the possible causes for high attrition rates for Computer Science students. It is a serious problem in universities that must be addressed if the need for technologically competent professionals is to be met.
Characterizing a national community web
Authors: Gomes Daniel , Silva Mário J.
Published: November 2005

This article presents a characterization of the community Web of the people of Portugal. We defined criteria for delimiting this Web based on our past experience of crawling pages related to Portugal and collected over 3.2 million documents from 46,000 sites satisfying those criteria. Our characterization was derived from this crawl. We describe the rules that we established for defining the boundaries of this community Web and the methodology used to gather statistics. Statistics cover the number and domain distribution of sites; the number, type and size distribution of text documents; and the linkage structure of this Web. We also show how crawling constraints and abnormal situations on the Web can influence the statistics.
Keystroke analysis of free text
Authors: Gunetti Daniele , Picardi Claudia
Published: November 2005

Keystroke dynamics can be useful to ascertain personal identity even
after
an authentication phase has been passed, provided that we are able to deal with the typing rhythms of free text, chosen and entered by users without any specific constraint. In this paper we present a method to compare typing samples of free text that can be used to verify personal identity. We have tested our technique with a wide set of experiments on 205 individuals, obtaining a False Alarm Rate of less than 5% and an Impostor Pass Rate of less than 0.005%. Different trade-offs are, however, possible. Our approach can rely on what is typed by people because of their normal job, and a few lines of text, even collected in different working sessions, are sufficient to reach a high level of accuracy, which improves proportionally to the amount of available information: As a consequence, we argue that our method can be useful in computer security as a complementary or alternative way to user authentication and as an aid to intrusion detection.
On dynamic plug-in loading with Ada 95 and Ada 2005
Authors: Comar Cyrille , Rogers Pat
Published: November 2005

Maintenance of high-availability systems (e.g., servers) requires the ability to modify, enhance, or correct parts of the application without having to stop and re-link the entire system. This capability is relatively straight-forward with interpreted languages or virtual-machine based languages such as Java, in which new code is loaded upon demand. In languages typically implemented with static executable images this capability can be offered though dynamically loaded/linked libraries ("DLLs"). However, in practice it is impractical to make full use of this capability because the protocol for invoking subprograms in a DLL is very low-level and unsafe. In the case of Ada, global coherency requirements and elaboration ordering constraints add an additional degree of complexity over less strict/safe languages.
Windows disk drive recovery with Ada95
Authors: Nyberg Karl
Published: November 2005

This note is a little documentary case of using Ada95 to develop a small utility to recover data from a FAT (File Allocation Table) formatted file system on a Windows 98 disk drive.
Reusable software components
Authors: Levine Trudy
Published: November 2005

This column consists of our yearly listing of sources for reusable software components. As always, no recommendation or guarantee by this column is implied.
PL-detective
Authors: Diwan Amer , Waite William M. , Jackson Michele H. , Dickerson Jacob
Published: November 2005

The educational literature recognizes that people go through a number of stages in their intellectual development. During the first stage, called
received knowledge
or
dualism
, people expect knowledge to be handed to them by authority figures (thus “received”) and think in terms of black and white (thus “dualism”). Our experience indicates that many computer science students are at this first stage of learning. To help students move beyond this stage, we describe a system and strategy, the PL-Detective, to be used in a Concepts of Programming Languages course. Assignments using this system directly confront students with the notion that they can create knowledge via interactions with the PL-Detective and that discussion with students (rather than asking the instructor) is an effective way of learning how to reason. We present experimental results that show that the PL-Detective is effective in helping students move beyond the stage of received knowledge.
Sentence-based natural language plagiarism detection
Authors: White Daniel R. , Joy Mike S.
Published: November 2005

With the increasing levels of access to higher education in the United Kingdom, larger class sizes make it unrealistic for tutors to be expected to identify instances of peer-to-peer plagiarism by eye and so automated solutions to the problem are required. This document details a novel algorithm for comparison of suspect documents at a sentence level and has been implemented as a component of plagiarism detection software for detecting similarities in both natural language documents and comments within program source-code. The algorithm is capable of detecting sophisticated obfuscation (such as paraphrasing, reordering, merging, and splitting sentences) as well as direct copying. The implemented algorithm has also been used to successfully detect plagiarism on real assignments at the university. The software has been evaluated by comparison with other plagiarism detection tools.
Stateless programming as a motif for teaching computer science
Authors: Cohen Avi
Published: November 2005

With the development of XML Web Services, the Internet could
become an integral part of and the basis for teaching computer
science and software engineering.

The approach has been applied to a university course for
students studying introduction to computer science from the point
of view of software development in a stateless, Internet
environment. The feedback obtained from the course attests to its
success.

This article is an attempt to focus attention on stateless
programming and to give this paradigm its appropriate status in
computer science studies. The course could provide an alternative
to traditional patterns of computer science. The walk-through
presented here is a way of demonstrating this new paradigm.

The starting point for the course is the understanding of the
Internet environment and the stateless HTTP request, followed by
the use and development of XML Web Services integrated with XML and
XML schemas, databases and SQL language.
Introducing embedded software and systems education and advanced learning technology in an engineering curriculum
Authors: Sztipanovits Janos , Biswas Gautam , Frampton Ken , Gokhale Aniruddha , Howard Larry , Karsai Gabor , Koo T. John , Koutsoukos Xenofon , Schmidt Douglas C.
Published: November 2005

Embedded software and systems are at the intersection of electrical engineering, computer engineering, and computer science, with, increasing importance, in mechanical engineering. Despite the clear need for knowledge of systems modeling and analysis (covered in electrical and other engineering disciplines) and analysis of computational processes (covered in computer science), few academic programs have integrated the two disciplines into a cohesive program of study. This paper describes the efforts conducted at Vanderbilt University to establish a curriculum that addresses the needs of embedded software and systems. Given the compartmentalized nature of traditional engineering schools, where each discipline has an independent program of study, we have had to devise innovative ways to bring together the two disciplines. The paper also describes our current efforts in using learning technology to construct, manage, and deliver sophisticated computer-aided learning modules that can supplement the traditional course structure in the individual disciplines through out-of-class and in-class use.
Guidelines for a graduate curriculum on embedded software and systems
Authors: Caspi P. , Sangiovanni-Vincentelli A. , Almeida L. , Benveniste A. , Bouyssounouse B. , Buttazzo G. , Crnkovic I. , Damm W. , Engblom J. , Folher G. , Garcia-Valls M. , Kopetz H. , Lakhnech Y. , Laroussinie F. , Lavagno L. , Lipari G. , Maraninchi F. , Peti Ph. , Puente J. de la , Scaife N. , Sifakis J. , de Simone R. , Torngren M. , Veríssimo P. , Wellings A. J. , Wilhelm R. , Willemse T. , Yi W.
Published: November 2005

The design of embedded real-time systems requires skills from multiple specific disciplines, including, but not limited to, control, computer science, and electronics. This often involves experts from differing backgrounds, who do not recognize that they address similar, if not identical, issues from complementary angles. Design methodologies are lacking in rigor and discipline so that demonstrating correctness of an embedded design, if at all possible, is a very expensive proposition that may delay significantly the introduction of a critical product. While the economic importance of embedded systems is widely acknowledged, academia has not paid enough attention to the education of a community of high-quality embedded system designers, an obvious difficulty being the need of interdisciplinarity in a period where specialization has been the target of most education systems. This paper presents the reflections that took place in the European Network of Excellence Artist leading us to propose principles and structured contents for building curricula on embedded software and systems.
The embedded software consortium of taiwan
Authors: Huang Tai-Yi , King Chung-Ta , Lin Youn-Long Steve , Hwang Yin-Tsung
Published: November 2005

The advancement of semiconductor manufacturing technology makes it practical to place a traditional board-level embedded system on a single chip. The evolvement of system-on-chip (SoC) techniques presents new challenges for integrated circuit designs as well as embedded software and systems. To address these challenges, the Ministry of Education (MOE) of Taiwan has been running the VLSI Circuits and Systems Education Program since 1996. This program adopts a top-down approach by forming six domain-specific, intercollegiate consortia. The Embedded Software (ESW) consortium addresses the challenges of embedded software for SoC systems. This paper first introduces the six-consortium architecture and the organization and programs of ESW. We next describe the embedded software curriculum developed by ESW. This curriculum will later be implemented in most universities and colleges in Taiwan to promote the capabilities of embedded software design and implementations. Finally, we present an execution summary of ESW 2004.
What is embedded systems and how should it be taught?---results from a didactic analysis
Authors: Grimheden Martin , Törngren Martin
Published: November 2005

This paper provides an analysis of embedded systems education using a didactic approach. Didactics is a field of educational studies mostly referring to research aimed at investigating what's unique with a particular subject and how this subject ought to be taught. From the analysis we conclude that embedded systems has a thematic identity and a functional legitimacy. This implies that the subject would benefit from being taught with an exemplifying selection and using an interactive communication, meaning that the education should move from teaching “something of everything” toward “everything of something.” The interactive communication aims at adapting the education toward the individual student, which is feasible if using educational methods inspired by project-organized and problem-based learning. This educational setting is also advantageous as it prepares the students for a future career as embedded system engineers. The conclusions drawn from the analysis correlate with our own experiences from education in mechatronics as well as with a recently published study of 21 companies in Sweden dealing with industrial software engineering.
Reducing data cache leakage energy using a compiler-based approach
Authors: Zhang Wei , Kandemir Mahmut , Karakoy Mustafa , Chen Guangyu
Published: November 2005

Silicon technology advances have made it possible to pack millions of transistors---switching at high clock speeds---on a single chip. While these advances bring unprecedented performance to electronic products, they also pose difficult power/energy consumption problems. For example, large number of transistors in dense on-chip cache memories consume significant static (leakage) power even if the cache is not used by the current computation. While previous compiler research studied code and data restructuring for improving data cache performance, to our knowledge, there exists no compiler-based study that targets data cache leakage power consumption. In this paper, we present code restructuring techniques for array-based and pointer-intensive applications for reducing data cache leakage energy consumption. The idea is to let the compiler analyze the application code and insert instructions that turn off cache lines that keep variables not used by the current computation. This turning-off does not destroy contents of a cache line and waking up the cache line (when it is accessed later) does not incur much overhead. Due to inherent data locality in applications, we find that, at a given time, only a small portion of the data cache needs to be active; the remaining part can be placed into a leakage-saving mode (state); i.e., they can be turned off. Our experimental results indicate that the proposed compiler-based strategy reduces the cache energy consumption significantly. We also demonstrate how different compiler optimizations can increase the effectiveness of our strategy.
Dynamic delay-constrained minimum-energy dissemination in wireless sensor networks
Authors: Kim Hyung Seok , Abdelzaher Tarek F. , Kwon Wook Hyun
Published: November 2005

Disseminating data generated by sensors to users is one of useful functions of sensor networks. In probable real-time applications of sensor networks, multiple mobile users should receive data within their end-to-end delay constraint. In this paper, we propose a dynamic DElay-constrained minimum-Energy Dissemination (DEED) scheme. A dissemination tree (d-tree) is updated in a distributed way without regenerating the tree from scratch, such that energy consumption of the tree is minimized while satisfying end-to-end delay constraints. The d-tree is adjusted using delay estimation based on geometric distance. DEED increases the probability that packets arrive at users within an upper-bound end-to-end delay (UBED) and minimizes energy consumption in both building the d-tree and disseminating data to mobile sinks. Evaluation results show that DEED makes each node consume small energy resources and maintains fewer UBED misses when compared to Directed Diffusion and other baselines for sensor networks.
Mixin modules in a call-by-value setting
Authors: Hirschowitz Tom , Leroy Xavier
Published: November 2005

The ML module system provides powerful parameterization facilities, but lacks the ability to split mutually recursive definitions across modules and provides insufficient support for incremental programming. A promising approach to solve these issues is Ancona and Zucca's mixin module calculus
CMS
. However, the straightforward way to adapt it to ML fails, because it allows arbitrary recursive definitions to appear at any time, which ML does not otherwise support. In this article, we enrich
CMS
with a refined type system that controls recursive definitions through the use of dependency graphs. We then develop and prove sound a separate compilation scheme, directed by dependency graphs, that translates mixin modules down to a call-by-value λ-calculus extended with a nonstandard let rec construct.
Link-time binary rewriting techniques for program compaction
Authors: De Sutter Bjorn , De Bus Bruno , De Bosschere Koen
Published: November 2005

Small program size is an important requirement for embedded systems with limited amounts of memory. We describe how link-time compaction through binary rewriting can achieve code size reductions of up to 62% for statically bound languages such as C, C++, and Fortran, without compromising on performance. We demonstrate how the limited amount of information about a program at link time can be exploited to overcome overhead resulting from separate compilation. This is done with scalable, cost-effective, whole-program analyses, optimizations, and duplicate code and data elimination techniques. The discussed techniques are evaluated and their cost-effectiveness is quantified with Squeeze++, a prototype link-time compactor.
An accurate cost model for guiding data locality transformations
Authors: Vera Xavier , Abella Jaume , Llosa Josep , González Antonio
Published: November 2005

Caches have become increasingly important with the widening gap between main memory and processor speeds. Small and fast cache memories are designed to bridge this discrepancy. However, they are only effective when programs exhibit sufficient data locality.The performance of the memory hierarchy can be improved by means of data and loop transformations. Tiling is a loop transformation that aims at reducing capacity misses by shortening the reuse distance. Padding is a data layout transformation targeted to reduce conflict misses.This article presents an accurate cost model that describes misses across different hierarchy levels and considers the effects of other hardware components such as branch predictors. The cost model drives the application of tiling and padding transformations. We combine the cost model with a genetic algorithm to compute the tile and pad factors that enhance the program performance.To validate our strategy, we ran experiments for a set of benchmarks on a large set of modern architectures. Our results show that this scheme is useful to optimize programs' performance. When compared to previous approaches, we observe that with a reasonable compile-time overhead, our approach gives significant performance improvements for all studied kernels on all architectures.
Kolmogorov complexity leads to a representation theorem for idempotent probabilities (σ-maxitive measures)
Authors: Kreinovich Vladik , Longpré Luc
Published: November 2005

In many application areas, it is important to consider maxitive measures (idempotent probabilities), i.e., mappings
m
for which
m
(
A
∪
B
) = max(
m
(
A
),
m
(
B
)). In his papers, J. H. Lutz has used Kolmogorov complexity to show that for constructively defined sets
A
, one maxitive measure - fractal dimension - can be represented as
m
(
A
) = sup
f
(
x
). We show that a similar representation is possible for an arbitrary maxitive measure.
SIGACT news logic column 13
Authors: Pucella Riccardo
Published: November 2005

For this issue, Nick Papanikolaou brings us an introduction to the subject of quantum logic and a survey of the relevant literature, including a discussion of logics for specification and analysis of quantum information systems.
Quality-of-Service versus Realtime
Authors: Gwinn Joseph M.
Published: November 2005

That QoS and Realtime are mutually exclusive is shown by use of simple queuing theory. QoS mechanisms will not be active in the light to moderate (up to 50% average and 80% peak occupancy) communications load regime used by realtime systems, as by definition there is enough communications capacity to satisfy any and all requests in that moderate-load regime. QoS is required only when communications system path occupancy exceeds about 80%, where offered traffic must be forcibly shaped or deferred to fit the insufficient available communications capacity. No realtime system should be designed to operate in that regime, because the resulting large and random-appearing variations in latency make it impossible to achieve realtime behavior, or in many cases, to even achieve stable system operation.
Performance analysis of an admission controller for CPU- and I/O-intensive applications in self-managing computer systems
Authors: Nijim Mais , Xie Tao , Qin Xiao
Published: November 2005

With rapid advances in processing power, network bandwidth, and storage capacity, computer systems are increasingly becoming extremely complex. Consequently, it becomes expensive and difficult for human beings to manually manage complex computer systems. This problem can be effectively tackled by self-managing computer systems, which are intended to meet high performance requirements in a dynamic computing environment. In this paper, we develop a performance model for self-manage computer systems under dynamic workload conditions, where both CPU- and I/O-intensive applications are running in the systems. In particular, we design in this paper a 2-dimenssional Markov chain model with two different arrival and service rate of CPU- and I/O-intensive jobs. Importantly, two serving probabilities with respect to CPU-and I/O intensive jobs are derived. To validate the analytical model, we developed an adaptive admission controller in which the model is incorporated. Experimental results demonstratively show that the controller is capable of achieving high performance for computer systems under workloads exhibiting high variability.
Tradeoffs in buffering speculative memory state for thread-level speculation in multiprocessors
Authors: Garzarán María Jesús , Prvulovic Milos , Llabería José María , Viñals Víctor , Rauchwerger Lawrence , Torrellas Josep
Published: November 2005

Thread-Level Speculation (TLS) provides architectural support to aggressively run hard-to-analyze code in parallel. As speculative tasks run concurrently, they generate unsafe or speculative
memory state
that needs to be separately buffered and managed in the presence of distributed caches and buffers. Such a state may contain multiple versions of the same variable. In this paper, we introduce a novel taxonomy of approaches to buffer and manage multiversion speculative memory state in multiprocessors. We also present a detailed complexity-benefit tradeoff analysis of the different approaches. Finally, we use numerical applications to evaluate the performance of the approaches under a single architectural framework. Our key insights are that support for buffering the state of multiple speculative tasks and versions per processor is more complexity-effective than support for lazily merging the state of tasks with main memory. Moreover, both supports can be gainfully combined and, in large machines, their effect is nearly fully additive. Finally, the more complex support for storing future state in the main memory can boost performance when buffers are under pressure, but hurts performance when squashes are frequent.
Merging path and gshare indexing in perceptron branch prediction
Authors: Tarjan David , Skadron Kevin
Published: November 2005

We introduce the
hashed
perceptron predictor, which merges the concepts behind the gshare, path-based and perceptron branch predictors. This predictor can achieve superior accuracy to a path-based and a global perceptron predictor, previously the most accurate dynamic branch predictors known in the literature. We also show how such a predictor can be ahead pipelined to yield one cycle effective latency. On the SPECint2000 set of benchmarks, the hashed perceptron predictor improves accuracy by up to 15.6% over a MAC-RHSP and 27.2% over a path-based neural predictor.
Pursuing scalability for
hypre
's conceptual interfaces
Authors: Falgout Robert D. , Jones Jim E. , Yang Ulrike Meier
Published: November 2005

The software library
hypre
provides high-performance preconditioners and solvers for the solution of large, sparse linear systems on massively parallel computers as well as conceptual interfaces that allow users to access the library in the way they naturally think about their problems. These interfaces include a stencil-based structured interface (Struct); a semistructured interface (semiStruct), which is appropriate for applications that are mostly structured, for example, block structured grids, composite grids in structured adaptive mesh refinement applications, and overset grids; and a finite element interface (FEI) for unstructured problems, as well as a conventional linear-algebraic interface (IJ). It is extremely important to provide an efficient, scalable implementation of these interfaces in order to support the scalable solvers of the library, especially when using tens of thousands of processors. This article describes the data structures, parallel implementation, and resulting performance of the IJ, Struct and semiStruct interfaces. It investigates their scalability, presents successes as well as pitfalls of some of the approaches and suggests ways of dealing with them.
From DQ to EQ
Authors: Kim Yong Jin , Kishore Rajiv , Sanders G. Lawrence
Published: November 2005

A fix for irrelevant information, cognitive overhead, and disorientation---common gremlins endured by every e-business system user.
Personalization technologies
Authors: Adomavicius Gediminas , Tuzhilin Alexander
Published: November 2005

By leveraging customer reactions to personalized products and services, companies continuously improve their personalization processes through an iterative feedback loop resulting in the `virtuous cycle' of personalization.
Did MGM really win the
Grokster
case?
Authors: Samuelson Pamela
Published: November 2005

The
Sony
safe harbor survived a tough challenge before the Supreme Court.
Software in Ireland
Authors: Cusumano Michael A.
Published: November 2005

A unique set of circumstances contributes to the recent success of the Irish software industry.
Academic dishonesty and the Internet
Authors: Ross Kenneth A.
Published: November 2005

The Internet provides new opportunities for cheating on computer science class projects.
Consumer power in the digital society
Authors: Zureik Elia , Mowshowitz Abbe
Published: November 2005

A shift in the balance of power brings with it increased potential for influence.
Community
Authors: Wellman Barry
Published: November 2005

Communities are networks of interpersonal ties that provide sociability, support, information, a sense of belonging, and social identity. Well into the 20th century, communities were equated with neighborhoods---bounded groups of people living near each other. This neighborhood-centered view of community made only partial sense because people have always had long-distance community ties either by traveling themselves or through connections with soldiers, artisans, peddlers, traders, marriage partners, shepherds, and the rich.
Education goes digital
Authors: Hiltz Starr Roxanne , Turoff Murray
Published: November 2005

Studying the transformation of education and its changing role in society.
Algorithms and data structures for flash memories
Authors: Gal Eran , Toledo Sivan
Published: November 2005

Flash memory is a type of electrically-erasable programmable read-only memory (EEPROM). Because flash memories are nonvolatile and relatively dense, they are now used to store files and other persistent objects in handheld computers, mobile phones, digital cameras, portable music players, and many other computer systems in which magnetic disks are inappropriate. Flash, like earlier EEPROM devices, suffers from two limitations. First, bits can only be cleared by erasing a large block of memory. Second, each block can only sustain a limited number of erasures, after which it can no longer reliably store data. Due to these limitations, sophisticated data structures and algorithms are required to effectively use flash memories. These algorithms and data structures support efficient not-in-place updates of data, reduce the number of erasures, and level the wear of the blocks in the device. This survey presents these algorithms and data structures, many of which have only been described in patents until now.
The power of explicit congestion notification
Authors: Kuzmanovic Aleksandar
Published: November 2005

Despite the fact that Explicit Congestion Notification (ECN) demonstrated a clear potential to substantially improve network performance, recent network measurements reveal an extremely poor
usage
of this option in today's Internet. In this paper, we analyze the roots of this phenomenon and develop a set of novel incentives to encourage network providers, end-hosts, and web servers to apply ECN.Initially, we examine a fundamental drawback of the current ECN specification, and demonstrate that the absence of ECN indications in TCP control packets can dramatically hinder system performance. While security reasons primarily prevent the usage of ECN bits in TCP SYN packets, we show that applying ECN to TCP SYN ACK packets can significantly improve system performance without introducing any novel security or stability side-effects. Our network experiments on a cluster of web servers show a dramatic performance improvement over the existing ECN specification: throughput increases by more than 40%, while the average web response-time
simultaneously
decreases by nearly an order of magnitude.In light of the above finding, using large-scale simulations, modeling, and network experiments, we re-investigate the relevance of ECN, and provide a set of practical recommendations and insights: (i) ECN
systematically
improves the performance of all investigated AQM schemes; contrary to common belief, this particularly holds for RED. (ii) The impact of ECN is highest for web-only traffic mixes such that even a generic AQM algorithm with ECN support outperforms all non-ECN-enabled AQM schemes that we investigated. (iii) Primarily due to moderate queuing levels, the superiority of ECN over other AQM mechanisms largely holds for high-speed backbone routers, even in more general traffic scenarios. (iv) End-hosts that apply ECN can exercise the above performance benefits instantly, without waiting for the entire Internet community to support the option.
Profiling internet backbone traffic
Authors: Xu Kuai , Zhang Zhi-Li , Bhattacharyya Supratik
Published: November 2005

Recent spates of cyber-attacks and frequent emergence of applications affecting Internet traffic dynamics have made it imperative to develop effective techniques that can extract, and make sense of, significant communication patterns from Internet traffic data for use in network operations and security management. In this paper, we present a general methodology for building comprehensive behavior profiles of Internet backbone traffic in terms of communication patterns of end-hosts and services. Relying on data mining and information-theoretic techniques, the methodology consists of significant cluster extraction, automatic behavior classification and structural modeling for in-depth interpretive analyses. We validate the methodology using data sets from the core of the Internet. The results demonstrate that it indeed can identify common traffic profiles as well as anomalous behavior patterns that are of interest to network operators and security analysts.