bluuebunny/crossref_metadata_2025 huggingface dataset:
Do students know best?
Authors: Whaley H. , Grice S.
Published: September 2007

Computing departments are in an exclusive position to utilise students, as it is the nature of the subject area that ensures students have both the knowledge of the course material and the ability to develop resources for online environments. They have greater computer literacy levels than peers in other domains and can adapt the skills learnt through their curriculum to the context of online resource creation for education.
Transforming a high school student project in computer science into a significant scientific achievement
Authors: Raveh Barak , Haberman Bruria , Yehezkel Cecile
Published: September 2007

A special program for high school has been in operation in Israel whose aim is to expose young students to the field of computing. During their studies the students are required to develop a software project, and thus gain experience in software design. In the past students lacked proper guidance in technologically demanding projects. Here we describe how the work of a student who chose to develop an engine for automatic completion of sentences by the computer was enhanced through cooperation with academia in the innovative "Computer Science, Academia and Industry" educational program. Albeit highly talented, the student lacked necessary formal knowledge in advanced computing technologies. A graduate student who specializes in the field has mentored the high school student throughout design and implementation phase, enabling him to grasp an intuitive understanding of state of the art algorithms, and contribute creative ideas of his own, resulting in an award-winning project of scientific significance.
Highly interactive online study skills course
Authors: Halstensen Maths , Haug Frode
Published: September 2007

This poster describes the most important aspects concerning design and development of an highly interactive web based study skills course called
"Unstuck"
which is a work in progress to be finished June 2008.
"Unstuck"
is a project started by both teachers and students from Gjøvik University College and Telemark University College in Norway.

This project started in 2006 as a result of experience from more than 10 years of teaching students with insufficient study skills. In this course we aim to present the theory and practice of "How to study" in an exiting interactive multimedia environment.

Telemark University College has since 2002 educated students starting with only a certificate of completed apprenticeship. In 2007, approximately 70% of all the students studying electrical engineering have this type of background, and insufficient study skills are a challenge.

"Unstuck"
will be used by students in secondary High school and University Colleges in Telemark, and Gjøvik in Norway from August 2008.

What makes Unstuck different from other study skills courses? The content of Unstuck is similar to other courses; the difference is the way the content is presented for the students. Unstuck will contain intensive use of interaction with the student, which involves various active actions such as pressing buttons, placing objects to specific locations on the screen, marking key words etc. Videos are used to demonstrate how to study in practice and to illustrate class room and other study related situations.

At the end of the course the student will have a short test (quiz). If the student don't pass, it is possible to immediately repeat relevant sections, and subsequently repeat the test.
"Unstuck"
will be an easy to use interactive multimedia study skills course on the weB.
An account of the use of synoptic assessment for students in the area of databases at level 2
Authors: Gorra Andrea , Lazarevski Sanela , Campbell Jackie
Published: September 2007

The purpose of this poster is to share innovative teaching methods at Leeds Metropolitan University in the Innovation North Faculty of Information and Technology (INN Faculty). An explorative study has been undertaken to provide an initial evaluation of the use of synoptic assessments within the subject area of Computing.

Synoptic assessments, also known as integrated assessments, help to enable students to make connections between modules, to increase the level of student engagement and to provide teaching staff with the opportunity to adopt a holistic approach to delivering modules. This type of assessment pulls together independent assessments from a number of modules into a single assessment exercise.

Synoptic assessment is driven by providing an environment for synoptic learning via a supporting course structure. For this reason, the course structures of the Innovation North Faculty are described for all three undergraduate levels. See Table 1 for an example of the course structure for Level 2.

A series of semi-structured interviews were conducted to learn about staff and students' perspectives on integrated assessments and their views of the learning environment in general. Twenty computing students were approached to talk about their experience with and opinions of integrated assessments. In addition to the student interviews, ten members of academic teaching staff were interviewed.

The findings are the result of an exploratory study and should be taken as indicative. The use of synoptic assessments within the INN Faculty is currently evaluated in depth as part of the CETL ALiC project [1, 2] and results will be published in the near future. The analysis of the interviews indicates that students perceive the delivery pattern of block teaching and pairing of modules as beneficial. The main reason for this is that it enables students to concentrate on two subject areas at a time in comparison to the traditional semester structure of four modules. Potential areas for concern are the nature of modules that are paired and a fair marking scheme. Teaching staff feel that the synoptic assessment enabled by a case study has worked well for the students. However, issues with timetabling need to be considered, and dependencies between the paired modules need to be avoided.
'But i don't read text printed in braille font'...
Authors: Dickinson Anne
Published: September 2007

The author works in Coventry University and has been engaged in tutoring a student with disabilities who had enrolled for a degree in Business and IT at Coventry University. To do this, the author drew upon previous experiences in the Further Education (FE) sector at a College in the Midlands, where she taught Information Technology (IT) to diverse groups of students who had varied abilities. The ages of the FE students ranged from pre-16, visiting the College from a local special school to attend "taster" sessions, to adults, some of whom were seniors, attending a day centre for disabled adults that had a special arrangement for College tutors to give classes.

The degree student was a white cane user, read Braille and navigated the computer with screen reader software. During her time at University, she took on an ambassadorial role: she gave guided tours to prospective students around the University campus during open days! From time to time she would recount stories that she described as amusing but which clearly showed ignorance on the part of her tutors. The title of this presentation is taken from one of her anecdotes.

The Degree course in Business and IT had several workshops in Computing including statistics where spreadsheets and specialist software were used. The author was asked to tutor the student for the IT workshops of a year-long module. This included translating the instructional handouts from mouse-based to keyboard-based, being aware of potential problems with specialist software and the quirks of the online learning system (WebCT) [1] and finding ways of working around them all. This poster shows some of the issues related to the student's stories, the creating and translating of instructions for keyboard use and navigating the keyboard using JAWS.
Prediction of modulators of pyruvate kinase in smiles text using aprori methods
Authors: Caronna Jason S. , Sharma Rojita , Marra Jonathan D. , Iuorno Virginia L. , Herbert Katherine G. , Toney Jeffrey H.
Published: September 2007

Pyruvate kinase is an enzyme that catalyzes the formation of pyruvate from phosphenolpyruvate in glycolysis. There is a wealth of data on the activity of certain molecules and their effects on pyruvate kinase. This project aims to create an application that uses a pyruvate kinase dataset to determine the nature of unidentified molecules; whether or not they would be activators or inhibitors of this enzyme. This application uses an Apriori algorithm to identify or predict modulators of pyruvate kinase. This initial study focuses on simplified molecular input line entry specification (SMILES) text as target data to be mined. The three dimensional structure of pyruvate kinase is known and accessible though the Protein Data Bank (e.g., PDB code IA3W).
Accessibility tools
Authors: Barker Guy , Prey Jane
Published: September 2007

There is great interest in Microsoft in developing applications and tools that enable better accessibility to technology to non-traditional users. We will demonstrate a set of tools [http://herbi.org/default.htm] that have been developed by various people in MS who are passionate about accessibility. These tools are in developmental form, but we are anxious to have the computing community look at them, use them and provide us with feedback on how to make them better.
Network educationware demonstration
Authors: Pullen J. Mark
Published: September 2007

Network EducationWare (NEW) is a powerful and robust open-source multimedia system for synchronous Internet distance education. It supports blended presentations in a form we call
simulteaching
, where some students are in a traditional classroom and others participate in real time over the Internet. It also records the class as presented, so that students can attend class delayed in time. NEW has been designed to be highly modular and to make effective use of both network bandwidth and human time. Reference [1] describes how George Mason University has used NEW to offer a popular and innovative MS degree in Computer Science, at low cost.

NEW consists of
multi-platform, open source
software that runs on inexpensive Windows and Linux computers. It implements both synchronous and asynchronous paradigms for
distance education
in a way that requires little additional effort on the part of the instructor and little additional cost for the institution, yet provides
greatly increased accessibility
to students and therefore promotes
wider access
to graduate computer science education.

NEW is freely available to the Computer Science education community. Some important features which make it attractive are:

• Works over dialup modem and most commercial Internet services, allowing live participation, record, and playback at any site.

• Provides access to students at home or office, even through firewalls and network address translation (NAT) systems.

• Features Web-based access with LDAP authentication and an open source course management database.

• Audio and whiteboard interfaces with floor control and text chat panel allow full interaction with students over the Internet and require minimal learning time for faculty (video also is available with broadband Internet).

• Supports authoring of graphic materials from any application.

• Web-based Course Management system simplifies teaching, learning, and administration.

.

This demonstration will feature the NEW clients for both Windows and Linux, in operation with the NEW Live and Playback servers over a local wireless network (see figure below for operational configuration). The NEW software will be available during the demonstration for installation and operation on attendees' laptop computers.
Introducing propositional logic and queueing theory with the infotraffic interactive learning environments
Authors: Arnold Ruedi
Published: September 2007

InfoTraffic [2] is a collection of learning environments forteaching fundamental concepts of computer science and mathematics. So far, the two programs LogicTraffic, targeted at propositional logic, and QueueTraffic, targeted at queueing theory have been released
1
. Both are freely availableand can be downloaded (along with teaching materials) from [1]. This demonstration abstract gives a very brief introductionto these two programs and their use in class.
From classes to code
Authors: Paterson James H. , Haddow John
Published: September 2007

This paper describes provision of support for the implementation of fundamental class relationships through the use of a tool previously created for teaching design patterns.
Teaching concurrency and nondeterminism with spin
Authors: Ben-Ari Mordechai
Published: September 2007

The tutorial will familiarize the participants with the use of the Spin model checker in teaching concepts such as concurrency, verification and nondeterminism. They will also learn to use pedagogical software tools that I built based upon Spin: the jSpin environment for developing and verifying concurrent programs; SpinSpider, a tool for generating graphical representations of state diagrams of concurrent programs; VN, a tool for "experiencing" the nondeterminism of finite automata.
A roadmap for comprehensive online privacy policy management
Authors: Antón Annie I. , Bertino Elisa , Li Ninghui , Yu Ting
Published: September 2007

A framework supporting the privacy policy life cycle helps guide the kind of research to consider before sound privacy answers may be realized.
Computing is a natural science
Authors: Denning Peter J.
Published: September 2007

Information processes and computation continue to be found abundantly in the deep structures of many fields. Computing is not---in fact, never was---a science only of the artificial.
Games for science and engineering education
Authors: Mayo Merrilea J.
Published: September 2007

Video games can teach science and engineering better than lectures. Are they a cure for a numbing 200-person class?
A collection of kinesthetic learning activities for a course on distributed computing
Authors: Sivilotti Paolo A. G. , Pike Scott M.
Published: September 2007

Kinesthetic learning is a process where students learn by actively carrying out physical activities rather than by passively listening to lectures. Pedagogical research has indicated that kinesthetic learning is a fundamental, powerful, and ubiquitous learning style. It resonates with many students across all disciplines and levels of education. The adoption of kinesthetic approaches in college classrooms, however, has been hampered by the difficulty of designing effective activities, as well as the perceived challenges of coordinating these activities. On the other hand, courses on distributed computing, by the very nature of the material they cover, are uniquely suited to exploiting this learning technique. We have developed and piloted a collection of kinesthetic activities for a senior undergraduate or graduate-level course on distributed systems. We give detailed descriptions of these exercises and discuss factors that contribute to their success (or failure). Our hope is that others will adopt these particular activities in their own distributed systems courses as well as use these examples as a pattern for developing new activities.
Modeling and managing changes in text databases
Authors: Ipeirotis Panagiotis G. , Ntoulas Alexandros , Cho Junghoo , Gravano Luis
Published: September 2007

Large amounts of (often valuable) information are stored in web-accessible text databases. “Metasearchers” provide unified interfaces to query multiple such databases at once. For efficiency, metasearchers rely on succinct statistical summaries of the database contents to select the best databases for each query. So far, database selection research has largely assumed that databases are static, so the associated statistical summaries do not evolve over time. However, databases are rarely static and the statistical summaries that describe their contents need to be updated periodically to reflect content changes. In this article, we first report the results of a study showing how the content summaries of 152 real web databases evolved over a period of 52 weeks. Then, we show how to use “survival analysis” techniques in general, and Cox's proportional hazards regression in particular, to model database changes over time and predict when we should update each content summary. Finally, we exploit our change model to devise update schedules that keep the summaries up to date by contacting databases only when needed, and then we evaluate the quality of our schedules experimentally over real web databases.
Range search on multidimensional uncertain data
Authors: Tao Yufei , Xiao Xiaokui , Cheng Reynold
Published: September 2007

In an uncertain database, every object
o
is associated with a probability density function, which describes the likelihood that
o
appears at each position in a multidimensional workspace. This article studies two types of range retrieval fundamental to many analytical tasks. Specifically, a nonfuzzy query returns all the objects that appear in a search region
r

q

with at least a certain probability
t

q

. On the other hand, given an uncertain object
q
, fuzzy search retrieves the set of objects that are within distance ε

q

from
q
with no less than probability
t

q

. The core of our methodology is a novel concept of “probabilistically constrained rectangle”, which permits effective pruning/validation of nonqualifying/qualifying data. We develop a new index structure called the U-tree for minimizing the query overhead. Our algorithmic findings are accompanied with a thorough theoretical analysis, which reveals valuable insight into the problem characteristics, and mathematically confirms the efficiency of our solutions. We verify the effectiveness of the proposed techniques with extensive experiments.
SQL query optimization through nested relational algebra
Authors: Cao Bin , Badia Antonio
Published: September 2007

Most research work on optimization of nested queries focuses on aggregate subqueries. In this article, we show that existing approaches are not adequate for nonaggregate subqueries, especially for those having multiple subqueries and certain comparison operators. We then propose a new efficient approach, the nested relational approach, based on the nested relational algebra. The nested relational approach treats all subqueries in a uniform manner, being able to deal with nested queries of any type and any level. We report on experimental work that confirms that existing approaches have difficulties dealing with nonaggregate subqueries, and that the nested relational approach offers better performance. We also discuss algebraic optimization rules for further optimizing the nested relational approach and the issue of integrating it into relational database systems.
Adapting the course "quality of information systems" to E.H.E.A guidelines
Authors: Piattini Mario , García Félix
Published: September 2007

Currently, organizations depend increasingly on the quality of information systems (IS) for the achieving of their main strategic goals. This is the driving force behind providing Computer engineers with the necessary training. We present some ideas and experiences about how the teaching of the course Information System Quality, which belongs to the 5
th
year of MSc degree in Computer Science, has been adjusted and adapted so as to comply with the directives of the European Higher Education Area (EHEA). Important lessons and points to consider in the future have come about from the above.
How to fail a programming assignment
Authors: Edmondson Carol
Published: September 2007

Computer programming courses at university usually require students to undertake assignments which involve the submission of a working program by a particular date. Each semester, for a variety of reasons, some students fail these programming assignments. This paper uses humour to illuminate some of the unsuccessful approaches to programming assignments taken by some of the computing students whom the author has taught.
Can user-centered interface design be applied to education?
Authors: Traver V. Javier
Published: September 2007

The principles behind the discipline of Human-Computer Interaction (HCI) may have applications well beyond the design of artifacts or their interfaces. We argue that the philosophy (and practice) of user-centered design (UCD) can (and should) pervade most human activities. Indeed, not only human-computer (and computer-mediated human communication) but also human-human communication may benefit from this perspective. In this paper we are particularly concerned with the application of UCD to the educational setting. The novel view in this work is that formal teaching and learning (of anything, at any level), might be improved if instructional design, in analogy to the usual interface design, is student-centered. The brief, but illustrative, experience of the author in an HCI course for university computer-science students is at the core motivation of this reflective work.
Curb your objects!
Authors: Jimeno Roberto , Jorge M. S. , Ortega-Arjona L.
Published: September 2007

The Orthodox Form for C# Classes (OFC#C) is an idiom proposed for the C# programming language that intends to provide its classes with a basic structure that assures a predictable behavior for creation, copy, and destruction of instances. When classes in C# are written it is desirable to build them in such a way that their instances produce objects which behave in predictable ways. Programmers tend to make mistakes when their objects behave at run time in the same way the they expect them to behave at write/compile time.
A root cause analysis interface for error reporting
Authors: Sturm D. , Beiss R. S.
Published: September 2007

We describe a web-based interface that facilitates entering and analyzing medical errors. It uses an interactive causal tree-building component. The interactive component allows a user to build a causal tree with any number of events and antecedents. This replaces a form-based approach that is limited to a predetermined number of events and antecedents. After the causal tree is completed, the user can save the tree to a database. Causal trees can be retrieved and rebuilt as well. We developed an algorithm that, given a data bank of reported errors, will help detect similar events. This facilitates recognizing patterns of errors.
Failures in complex systems
Authors: Kopec Danny , Tamang Suzanne
Published: September 2007

Computers are the pervasive technology of our time. As computers become critically tied to human life, it also becomes more important that interactions with them are under control. They are no longer a novelty, but are integrated into the fabric of our world, performing both high and low-level tasks. That is, computers may be used to eliminate heavy, redundant work and more sophisticated machines have been deployed to perform remote surgery or detect subterranean landmines in repopulated civilian areas. The increasing importance of computers in our lives means that it is essential that the design of computer systems incorporates techniques that can ensure reliability, safety, and security. This paper will examine technological mishaps involving the use of computers. This review will include notorious software bugs that have affected finance, communication, transit, defense, health and medicine and other systems or industries. The sequences and etiology of these "accidents" will be discussed as well as how catastrophes may be avoided in the future through lessons and practices based on artificial intelligence research.
Enabling scalability and performance in a large scale CMP environment
Authors: Saha Bratin , Adl-Tabatabai Ali-Reza , Ghuloum Anwar , Rajagopalan Mohan , Hudson Richard L. , Petersen Leaf , Menon Vijay , Murphy Brian , Shpeisman Tatiana , Sprangle Eric , Rohillah Anwar , Carmean Doug , Fang Jesse
Published: September 2007

Hardware trends suggest that large-scale CMP architectures, with tens to hundreds of processing cores on a single piece of silicon, are iminent within the next decade. While existing CMP machines have traditionally been handled in the same way as SMPs, this magnitude of parallelism introduces several fundamental challenges at the architectural level and this, in turn, translates to novel challenges in the design of the software stack for these platforms. This paper presents the "Many Core Run Time" (McRT), a software prototype of an integrated language runtime that was designed to explore configurations of the software stack for enabling performance and scalability on large scale CMP platforms. This paper presents the architecture of McRT and discusses our experiences with the system, including experimental evaluation that lead to several interesting, non-intuitive findings, providing key insights about the structure of the system stack at this scale. A key contribution of this paper is to demonstrate how McRT enables near linear improvements in performance and scalability for desktop workloads such as the popular XviD encoder and a set of RMS (recognition, mining, and synthesis) applications. Another key contribution of this work is its use of McRT to explore non-traditional system configurations such as a light-weight executive in which McRT runs on "bare metal" and replaces the traditional OS. Such configurations are becoming an increasingly attractive alternative to leverage heterogeneous computing uints as seen in today's CPU-GPU configurations.
Comparing the performance of web server architectures
Authors: Pariag David , Brecht Tim , Harji Ashif , Buhr Peter , Shukla Amol , Cheriton David R.
Published: September 2007

In this paper, we extensively tune and then compare the performance of web servers based on three different server architectures. The μserver utilizes an event-driven architecture, Knot uses the highly-efficient Capriccio thread library to implement a thread-per-connection model, and WatPipe uses a hybrid of events and threads to implement a pipeline-based server that is similar in spirit to a staged event-driven architecture (SEDA) server like Haboob.

We describe modifications made to the Capriccio thread library to use Linux's zero-copy sendfile interface. We then introduce the SY mmetric Multi-Processor Event Driven (SYMPED) architecture in which relatively minor modifications are made to a single process event-driven (SPED) server (the μserver) to allow it to continue processing requests in the presence of blocking due to disk accesses. Finally, we describe our C++ implementation of WatPipe, which although utilizing a pipeline-based architecture, excludes the dynamic controls over event queues and thread pools used in SEDA. When comparing the performance of these three server architectures on the workload used in our study, we arrive at different conclusions than previous studies. In spite of recent improvements to threading libraries and our further improvements to Capriccio and Knot, both the event-based μserver and pipeline-based Wat-Pipe server provide better throughput (by about 18%). We also observe that when using blocking sockets to send data to clients, the performance obtained with some architectures is quite good and in one case is noticeably better than when using non-blocking sockets.
Container-based operating system virtualization
Authors: Soltesz Stephen , Pötzl Herbert , Fiuczynski Marc E. , Bavier Andy , Peterson Larry
Published: September 2007

Hypervisors, popularized by Xen and VMware, are quickly becoming commodity. They are appropriate for many usage scenarios, but there are scenarios that require system virtualization with high degrees of both
isolation
and
efficiency
. Examples include HPC clusters, the Grid, hosting centers, and PlanetLab. We present an alternative to hypervisors that is better suited to such scenarios. The approach is a synthesis of prior work on
resource containers
and
security containers
applied to general-purpose, time-shared operating systems. Examples of such container-based systems include Solaris 10, Virtuozzo for Linux, and Linux-VServer. As a representative instance of container-based systems, this paper describes the design and implementation of Linux-VServer. In addition, it contrasts the architecture of Linux-VServer with current generations of Xen, and shows how Linux-VServer provides comparable support for isolation and superior system efficiency.
Discrete control for safe execution of IT automation workflows
Authors: Wang Yin , Kelly Terence , Lafortune Stéphane
Published: September 2007

As information technology (IT) administration becomes increasingly complex, workflow technologies are gaining popularity for IT automation. Writing correct workflow programs is notoriously difficult. Although static analysis tools are available, fixing defects remains manual and error-prone. This paper applies discrete control theory to IT automation workflows. Discrete control detects flaws in workflows just as static analysis does, and more importantly it also allows safe execution of flawed workflows by dynamically avoiding run-time failures. Our approach can guarantee compliance with certain requirements and can partially decouple requirements from software, reducing the need to modify the latter if the former change. We have implemented a discrete control module for a real IT automation system. Experiments with workflows from a real production system and with randomly generated workflows show that our approach scales to workflows of practical size.
Authorizing applications in singularity
Authors: Wobber Ted , Yumerefendi Aydan , Abadi Martín , Birrell Andrew , Simon Daniel R.
Published: September 2007

We describe a new design for authorization in operating systems in which applications are first-class entities. In this design, principals reflect application identities. Access control lists are patterns that recognize principals. We present a security model that embodies this design in an experimental operating system, and we describe the implementation of our design and its performance in the context of this operating system.
Antiquity
Authors: Weatherspoon Hakim , Eaton Patrick , Chun Byung-Gon , Kubiatowicz John
Published: September 2007

Antiquity is a wide-area distributed storage system designed to provide a simple storage service for applications like file systems and back-up. The design assumes that all servers eventually fail and attempts to maintain data despite those failures. Antiquity uses a secure log to maintain data integrity, replicates each log on multiple servers for durability, and uses dynamic Byzantine fault-tolerant quorum protocols to ensure consistency among replicas. We present Antiquity's design and an experimental evaluation with global and local testbeds. Antiquity has been running for over two months on 400+ PlanetLab servers storing nearly 20,000 logs totaling more than 84 GB of data. Despite constant server churn, all logs remain durable.
A simple and efficient algorithm for cycle collection
Authors: Lin Chin-Yang , Hou Ting-Wei
Published: September 2007

The lack of collecting cyclic garbage is generally considered the major weakness of reference counting. Reference counted systems handle this problem by incorporating either a global tracing collector, or a "partial" tracing collector that considers only the cycle candidates but needs several traces on them. In particular, the latter has become a preferred one as it has better scalability and locality (no need to scan the entire heap). This paper presents a new "lightweight" cyclic reference counting algorithm, which is based on partial tracing and deals with the cycle problem in a simpler and more efficient way. By exploiting the lightweight hypothesis that considers a single sub-graph, instead of individual cycles, as the basic unit of cycle collection, the algorithm can detect garbage cycles in a single trace. In addition, we propose a technique for eliminating redundant scans over garbage objects, thus improving the efficiency of the algorithm. The pseudocode and its correctness proof are also presented. Finally, an implementation based on Jikes Research Virtual Machine is provided to demonstrate the effectiveness of the new algorithm.
WinHIPE
Authors: Pareja-Flores Cristóbal , Urquiza-Fuentes Jamie , Velázquez-Iturbide J. Ángel
Published: September 2007

The article describes an IDE for functional programming, called WinHIPE. It provides an interactive and flexible tracer, as well as a powerful visualization and animation system. The former tool is based on the rewriting model of evaluation, and the latter provides automatic generation of visualizations and animations, friendly support for customization, maintenance and exportation of animations to the Web, and facilities to cope with large scale. Its main advantage over other visualization systems is an effortless approach to animation creation and maintenance, based on generating visualizations and animations automatically, as a side effect of program execution. Finally, we briefly describe our experience using the system during several years in educational settings.
Report on the XML mining track at INEX 2005 and INEX 2006
Authors: Denoyer Ludovic , Gallinari Patrick
Published: September 2007

This article is a report concerning the two years of the XML Mining track at INEX (2005 and 2006). We focus here on the classification and clustering of XML documents. We detail these two tasks and the corpus used for this challenge and then present a summary of the different methods proposed by the participants. We last compare the results obtained during the two years of the track.
Performance and security lessons learned from virtualizing the alpha processor
Authors: Karger Paul A.
Published: September 2007

Virtualization has become much more important throughout the computer industry both to improve security and to support multiple workloads on the same hardware with effective isolation between those workloads. The most widely used chip architecture, the Intel and AMD x86 processors, have begun to support virtualization, but the initial implementations show some limitations. This paper examines the virtualization properties of the Alpha architecture with particular emphasis on features that improve performance and security. It shows how the Alpha's features of PALcode, address space numbers, software handling of translation buffer misses, lack of used and modified bits, and secure handling of unpredictable results all contribute to making virtualization of the Alpha particularly easy. The paper then compares the virtual architecture of the Alpha with Intel's and AMD's virtualization approaches for x86. It also comments briefly on Intel's virtualization technology for Itanium, IBM's zSeries and pSeries hypervisors and Sun's UltraSPARC virtualization. It particularly identifies some differences between translation buffers on x86 and translation buffers on VAX and Alpha that can have adverse performance consequences.
Ginger
Authors: Hilton Andrew D. , Roth Amir
Published: September 2007

The negative performance impact of branch mis-predictions can be reduced by exploiting control independence (CI). When a branch mis-predicts, the wrong-path instructions up to the point where control converges with the correct path are selectively squashed and replaced with correct-path instructions. Instructions beyond the convergence-point-the branch's control-independent (CI) instructions-are spared from squashing. Exploiting CI requires updating the input data dependences of CI instructions to reflect the selective removal and insertion of logically older instructions and transitively re-dispatching those CI instructions whose inputs have changed. This capability is generally called out-of-order renaming. Previously proposed CI designs use out-of-order renaming schemes that either consume excessive rename/dispatch bandwidth, can only be applied in limited cases, or incur a cost even when the branch would be correctly predicted.

Ginger is a CI design that is both general and bandwidth efficient. Ginger implements out-of-order renaming using tag rewriting, re-linking the input dependences of CI instructions as they sit in the window. To do this, Ginger halts the pipeline uses the idle map table read and write ports and the issue queue match lines and write lines to perform a register-tag "search-and-replace" operation. After a few cycles, the pipeline restarts and execution resumes with correct data dependences. Cycle-level simulation shows that Ginger out-performs previous CI designs, yielding geometric mean speedups over an aggressive non-CI processor of 5%, 12%, and 11%-on SPECint2000, MediaBench, and Comm-Bench-with speedups of 15% or greater on 11 of 46 programs.
Valgrind
Authors: Nethercote Nicholas , Seward Julian
Published: September 2007

Dynamic binary instrumentation (DBI) frameworks make it easy to build dynamic binary analysis (DBA) tools such as checkers and profilers. Much of the focus on DBI frameworks has been on performance; little attention has been paid to their capabilities. As a result, we believe the potential of DBI has not been fully exploited.

In this paper we describe Valgrind, a DBI framework designed for building heavyweight DBA tools. We focus on its unique support for
shadow values
-a powerful but previously little-studied and difficult-to-implement DBA technique, which requires a tool to shadow every register and memory value with another value that describes it. This support accounts for several crucial design features that distinguish Valgrind from other DBI frameworks. Because of these features, lightweight tools built with Valgrind run comparatively slowly, but Valgrind can be used to build more interesting, heavyweight tools that are difficult or impossible to build with other DBI frameworks such as Pin and DynamoRIO.
Thin slicing
Authors: Sridharan Manu , Fink Stephen J. , Bodik Rastislav
Published: September 2007

Program slicing systematically identifies parts of a program relevant to a seed statement. Unfortunately, slices of modern programs often grow too large for human consumption. We argue that unwieldy slices arise primarily from an overly broad definition of relevance, rather than from analysis imprecision. While a traditional slice includes all statements that may
affect
a point of interest, not all such statements appear equally relevant to a human.

As an improved method of finding relevant statements, we propose
thin slicing
. A thin slice consists only of
producer statements
for the seed,
i.e.
, those statements that help compute and copy avalue to the seed. Statements that explain why producers affect the seed are excluded. For example, for a seed that reads a value from a container object, a thin slice includes statements that store the value into the container, but excludes statements that manipulate pointers to the container itself. Thin slices can also be hierarchically expanded to include statements explaining how producers affect the seed, yielding a traditional slice in the limit.

We evaluated thin slicing for a set of debugging and program understanding tasks. The evaluation showed that thin slices usually included the desired statements for the tasks (
e.g.
, the buggy statement for a debugging task). Furthermore, in simulated use of a slicing tool, thin slices revealed desired statements after inspecting 3.3 times fewer statements than traditional slicing for our debugging tasks and 9.4 times fewer statements for our program understanding tasks. Finally, our thin slicing algorithm scales well to relatively large Java benchmarks, suggesting that thin slicing represents an attractive option for practical tools.
Automatic inversion generates divide-and-conquer parallel programs
Authors: Morita Kazutaka , Morihata Akimasa , Matsuzaki Kiminori , Hu Zhenjiang , Takeichi Masato
Published: September 2007

Divide-and-conquer algorithms are suitable for modern parallel machines, tending to have large amounts of inherent parallelism and working well with caches and deep memory hierarchies. Among others, list homomorphisms are a class of recursive functions on lists, which match very well with the divide-and-conquer paradigm. However, direct programming with list homomorphisms is a challenge for many programmers. In this paper, we propose and implement a novel systemthat can automatically derive cost-optimal list homomorphisms from a pair of sequential programs, based on the third homomorphism theorem. Our idea is to reduce extraction of list homomorphisms to derivation of weak right inverses. We show that a
weak right inverse
always exists and can be automatically generated from a wide class of sequential programs. We demonstrate our system with several nontrivial examples, including the maximum prefix sum problem, the prefix sum computation, the maximum segment sum problem, and the line-of-sight problem. The experimental results show practical efficiency of our automatic parallelization algorithm and good speedups of the generated parallel programs.
Combining events and threads for scalable network services implementation and evaluation of monadic, application-level concurrency primitives
Authors: Li Peng , Zdancewic Steve
Published: September 2007

This paper proposes to combine two seemingly opposed programming models for building massively concurrent network services: the event-driven model and the multithreaded model. The result is a hybrid design that offers the best of both worlds--the ease of use and expressiveness of threads and the flexibility and performance of events.

This paper shows how the hybrid model can be implemented entirely at the application level using
concurrency monads
in Haskell, which provides type-safe abstractions for both events and threads. This approach simplifies the development of massively concurrent software in a way that scales to real-world network services. The Haskell implementation supports exceptions, symmetrical multiprocessing, software transactional memory, asynchronous I/O mechanisms and application-level network protocol stacks. Experimental results demonstrate that this monad-based approach has good performance: the threads are extremely lightweight (scaling to ten million threads), and the I/O performance compares favorably to that of Linux NPTL. tens of thousands of simultaneous, mostly-idle client connections. Such massively-concurrent programs are difficult to implement, especially when other requirements, such as high performance and strong security, must also be met.
Reliable and efficient programming abstractions for wireless sensor networks
Authors: Kothari Nupur , Gummadi Ramakrishna , Millstein Todd , Govindan Ramesh
Published: September 2007

It is currently difficult to build practical and reliable programming systems out of distributed and resource-constrained sensor devices. The state of the art in today's sensornet programming is centered around a component-based language called nesC. nesC is a
node-level
language-a program is written for an individual node in the network-and nesC programs use the services of an operating system called TinyOS. We are pursuing an approach to programming sensor networks that significantly raises the level of abstraction over this practice. The critical change is one of perspective: rather than writing programs from the point of view of an individual node, programmers implement a
central
program that conceptually has access to the entire network. This approach pushes to the compiler the task of producing node-level programs that implement the desired behavio.

We present the Pleiades programming language, its compiler, and its runtime. The Pleiades language extends the C language with constructs that allow programmers to name and access node-local state within the network and to specify simple forms of concurrent execution. The compiler and runtime system cooperate to implement Pleiades programs efficiently and reliably. First, the compiler employs a novel program analysis to translate Pleiades programs into message-efficient units of work implemented in nesC. The Pleiades runtime system orchestrates execution of these units, using TinyOS services, across a network of sensor nodes. Second, the compiler and runtime system employ novel locking, deadlock detection, and deadlock recovery algorithms that guarantee serializability in the face of concurrent execution. We illustrate the readability, reliability and efficiency benefits of the Pleiades language through detailed experiments, and demonstrate that the Pleiades implementation of a realistic application performs similar to a hand-coded nesC version that contains more than ten times as much code.
Effective automatic parallelization of stencil computations
Authors: Krishnamoorthy Sriram , Baskaran Muthu , Bondhugula Uday , Ramanujam J. , Rountev Atanas , Sadayappan P
Published: September 2007

Performance optimization of stencil computations has been widely studied in the literature, since they occur in many computationally intensive scientific and engineering applications. Compiler frameworks have also been developed that can transform sequential stencil codes for optimization of data locality and parallelism. However, loop skewing is typically required in order to tile stencil codes along the time dimension, resulting in load imbalance in pipelined parallel execution of the tiles. In this paper, we develop an approach for automatic parallelization of stencil codes, that explicitly addresses the issue of load-balanced execution of tiles. Experimental results are provided that demonstrate the effectiveness of the approach.
Proving thread termination
Authors: Cook Byron , Podelski Andreas , Rybalchenko Andrey
Published: September 2007

Concurrent programs are often designed such that certain functions executing within critical threads must terminate. Examples of such cases can be found in operating systems, web servers, e-mail clients, etc. Unfortunately, no known automatic program termination prover supports a practical method of proving the termination of threads. In this paper we describe such a procedure. The procedure's scalability is achieved through the use of environment models that abstract away the surrounding threads. The procedure's accuracy is due to a novel method of incrementally constructing environment abstractions. Our method finds the conditions that a thread requires of its environment in order to establish termination by looking at the conditions necessary to prove that certain paths through the thread represent well-founded relations if executed
in isolation of the other threads
. The paper gives a description of experimental results using an implementation of our procedureon Windows device drivers and adescription of a previously unknown bug found withthe tool.
Offline compression for on-chip ram
Authors: Cooprider Nathan Dean , Regehr John David
Published: September 2007

We present
offline RAM compression
, an automated source-to-source transformation that reduces a program's data size. Statically allocated scalars, pointers, structures, and arrays are encoded and packed based on the results of a whole-program analysis in the value set and pointer set domains. We target embedded software written in C that relies heavily on static memory allocation and runs on Harvard-architecture microcontrollers supporting just a few KB of on-chip RAM. On a collection of embedded applications for AVR microcontrollers, our transformation reduces RAM usage by an average of 12%, in addition to a 10% reduction through a dead-data elimination pass that is also driven by our whole-program analysis, for a total RAM savings of 22%. We also developeda technique for giving developers access to a flexible spectrum of tradeoffs between RAM consumption, ROM consumption, and CPU efficiency. This technique is based on a model for estimating the cost/benefit ratio of compressing each variable and then selectively compressing only those variables that present a good value proposition in terms of the desired tradeoffs.