bluuebunny/crossref_metadata_2025 huggingface dataset:
TestU01
Authors: L'Ecuyer Pierre , Simard Richard
Published: September 2007

We introduceTestU01, a software library implemented in the ANSI C language, and offering a collection of utilities for the empirical statistical testing of uniform random number generators (RNGs). It provides general implementations of the classical statistical tests for RNGs, as well as several others tests proposed in the literature, and some original ones. Predefined tests suites for sequences of uniform random numbers over the interval (0, 1) and for bit sequences are available. Tools are also offered to perform systematic studies of the interaction between a specific test and the structure of the point sets produced by a given family of RNGs. That is, for a given kind of test and a given class of RNGs, to determine how large should be the sample size of the test, as a function of the generator's period length, before the generator starts to fail the test systematically. Finally, the library provides various types of generators implemented in generic form, as well as many specific generators proposed in the literature or found in widely used software. The tests can be applied to instances of the generators predefined in the library, or to user-defined generators, or to streams of random numbers produced by any kind of device or stored in files. Besides introducingTestU01, the article provides a survey and a classification of statistical tests for RNGs. It also applies batteries of tests to a long list of widely used RNGs.
Two-phase routing, scheduling and power control for wireless mesh networks with variable traffic
Authors: Kashyap Abhishek , Sengupta Sudipta , Bhatia Randeep , Kodialam M.
Published: September 2007

We consider the problem of joint routing, scheduling and transmission power assignment in multi-hop wireless mesh networks with unknown traffic. We assume the traffic is unknown, but the traffic matrix, which specifies the traffic load between every source-destination pair in the network, always lies inside a polytope defined by
hose
model constraints. The objective is to minimize the maximum of the total transmission power in the network over all traffic matrices in a given polytope. We propose efficient algorithms that compute a two-phase routing, schedule and power assignment, and prove the solution to be 3-approximation with respect to an optimal two-phase routing, scheduling and power assignment. We show via extensive simulations that the proposed algorithm has good performance at its worst operating traffic compared to an algorithm optimized for that traffic.
Sizing sketches
Authors: Wang Zhe , Dong Wei , Josephson William , Lv Qin , Charikar Moses , Li Kai
Published: September 2007

Sketches are compact data structures that can be used to estimate properties of the original data in building large-scale search engines and data analysis systems. Recent theoretical and experimental studies have shown that sketches constructed from feature vectors using randomized projections can effectively approximate L1 distance on the feature vectors with the Hamming distance on their sketches. Furthermore, such sketches can achieve good filtering accuracy while reducing the metadata space requirement and speeding up similarity searches by an order of magnitude. However, it is not clear how to choose the size of the sketches since it depends ondata type, dataset size, and desired filtering quality. In real systems designs, it is necessary to understand how to choose sketch size without the dataset, or at least without the whole datase.

This paper presents an analytical model and experimental results to help system designers make such design decisions. We present arank-based filtering model that describes the relationship between sketch size and data set size based on the dataset distance distribution. Our experimental results with several datasets including images, audio, and 3D shapes show that the model yields good, conservative predictions. We show that the parameters of the model can be set with a small sample data set and the resulting model can make good predictions for a large dataset. We illustrate how to apply the approach with a concrete example.
An algorithm for approximate counting using limited memory resources
Authors: Cvetkovski Andrej
Published: September 2007

This paper describes a randomized algorithm for approximate counting that preserves the same modest memory requirements of log(log n) bits per counter as the approximate counting algorithm introduced in the seminal paper of R. Morris (1978), and in addition, is characterized by (i) lower expected number of memory accesses and (ii) lower standard error on more than 99 percent of its counting range. An exact analysis of the relevant statistical properties of the algorithm is carried out. Performance evaluation via simulations is also provided to validate the presented theory.

Given its properties, the presented algorithm is suitable as a basic building block of data streaming applications having a large number of simultaneous counters and/or operating at very high speeds. As such, it is applicable to a wide range of measurement and monitoring operations, including performance monitoring of communication hardware, measurements for optimization in large database systems, and gathering statistics for data compression.
Wire speed packet classification without tcams: a few more registers (and a bit of logic) are enough
Authors: Dong Qunfeng , Banerjee Suman , Wang Jia , Agrawal Dheeraj
Published: September 2007

Packet classification is the foundation of many Internet functions such as QoS and security. A long thread of research has proposed efficient software-based solutions to this problem. Such software solutions are attractive because they require cheap memory systems for implementation, thus bringing down the overall cost of the system. In contrast, hardware-based solutions use more expensive memory systems, e.g., TCAMs, but are often preferred by router vendors for their faster classification speeds. The goal of this paper is to find a "best-of-both-worlds" solution -- a solution that incurs the cost of a software-based system and has the speed of a hardware-based one. Our proposed solution, called
smart rule cache
achieves this goal by using minimal hardware -- a few additional registers -- to cache
evolving
rules which preserve classification semantics, and additional logic to match incoming packets to these rules. Using real traffic traces and real rule sets from a tier-1 ISP, we show such a setup is sufficient to achieve very high hit ratios for fast classification in hardware. Cache miss ratios are 2 ∼ 4 orders of magnitude lower than flow cache schemes. Given its low cost and good performance, we believe our solution may create significant impact on current industry practice.
Evaluating SIP server performance
Authors: Nahum Erich M. , Tracey John , Wright Charles P.
Published: September 2007

SIP is a protocol of growing importance, with uses for VoIP, instant messaging, presence, and more. However, its performance is not well-studied or understood. In this extended abstract we overview our experimental evaluation of common SIP server scenarios using open-source SIP software such as OpenSER and SIP prunning on Linux.

We show performance varies greatly depending on the server scenario and how the protocol is used. Depending on the configuration, through put can vary from hundreds to thousands of operations per second. For example, we observe that the choice of stateless vs. stateful proxying, using TCP rather than UDP, or including MD5-based authentication can each can affect performance by a factor of 2-4. We also provide kernel and application profiles using Oprofile that help explain and illustrate processing costs. Finally, we provide a simple fix for transaction-stateful proxying that improves performance by a factor of 10. Full details can be found in our accompanying technical report.
Bottom-k sketches
Authors: Cohen Edith , Kaplan Haim
Published: September 2007

A
Bottom-k sketch
is a summary of a set of items with nonnegative weights. Each such summary allows us to compute approximate aggregates over the set of items. Bottom-
k
sketches are obtained by associating with each item in a ground set an independent random rank drawn from a probability distribution that depends on the weight of the item. For each subset of interest, the bottom-
k
sketch is the set of the
k
minimum ranked items and their ranks. Bottom-
k
sketches have numerous applications. We develop and analyze data structures and estimators for bottom-
k
sketches to facilitate their deployment. We develop novel estimators and algorithms that show that they are a superior alternative to other sketching methods in both efficiency of obtaining the sketches and the accuracy of the estimates derived from the sketches.
Generating representative ISP topologies from first-principles
Authors: Wang Chong , Byers John W.
Published: September 2007

Understanding and modeling the factors that underlie the growth and evolution of network topologies are basic questions that impinge upon capacity planning, forecasting, and protocol research. Early topology generation work focused on generating network-wide connectivity maps, either at the AS-level or the router-level, typically with an eye towards reproducing abstract properties of observed topologies. But recently, advocates of an alternative "first-principles" approach question the feasibility of realizing representative topologies with simple generative models that do not explicitly incorporate real-world constraints, such as the relative costs of router configurations, into the model. Our work synthesizes these two lines by designing a topology generation mechanism that incorporates first-principles constraints. Our goal is more modest than that of constructing an Internet-wide topology: we aim to generate representative topologies for single ISPs. However, our methods also go well beyond previous work, as we annotate these topologies with representative capacity and latency information. Taking only demand for network services over a given region as input, we propose a natural cost model for building and interconnecting PoPs and formulate the resulting optimization problem faced by an ISP. We devise hill-climbing heuristics for this problem and demonstrate that the solutions we obtain are quantitatively similar to those in measured router-level ISP topologies, with respect to both topological properties and fault-tolerance.
Asynchronous iterative solution for state-based performance metrics
Authors: de Jager Douglas V. , Bradley Jeremy T.
Published: September 2007

Solution of large sparse fixed-point problems, Mline over x = over x and Mline over x + line over b = over x, may be seen as underpinning many important performance-analysis calculations. These calculations include steady-state, passage-time and transient-time calculations in discrete-time Markov chains, continuous-time Markov chains and semi-Markov chains. In recent years, much work has been done to extend the application of asynchronous iterative fixed-point solution methods to many different contexts. This work has been motivated by the potential for faster solution, more efficient use of the communication channel and/or access to memory, and simplification of task management and programming. In this paper, we present theoretical developments which allow us to extend theapplication of asynchronous iterative solution methods to solve for the key performance metrics mentioned above-such that we may employ the full breadth of Chazan and Miranker's classes of asynchronous iterations.
Where have all the computer scientists gone?
Authors: van der Kuyl Chris
Published: September 2007

In recent years Universities all over the UK have been bemoaning the lack of undergraduates studying Computer Science. Is this all because of the internet bubble bursting or is Computer Science Education as we know it irrelevant? Professor van der Kuyl will explore these thoughts and look at the factors behind some of the more successful Computer Science degrees in recent years. In addition, he will explore the demand side of Computer Science education and pose the question: "What do employers really want?", as opposed to: "What do employers think they want?.
Inclusive thinking in computer science education
Authors: Hanson Vicki L.
Published: September 2007

On average, one in every five people has a disability. There is a growing, worldwide attention to the rights and needs of disabled users to access information technologies (IT). This technology is not simply for recreational use, but in many cases is a disabled user's lifeline to services and a path to employment. To address this issue, there has been enactment of legislation in countries worldwide aimed at making technology accessible. Such legislation has led to the creation of standards, guidelines, and checklists for accessibility, with the goal of having a common understanding of what is needed to make IT accessible and thereby enabling developers to create accessible applications.

Despite these efforts, however, technology remains largely unusable for people with disabilities. A number of factors may contribute to this state. Here we consider one of the key factors--that developers, in large part, do not understand and are not attuned to the needs of disabled users. The checklists are not intuitive and provide developers with little insight into the very real problems that disabled users have with computing. Moreover, these checklists address issues of "compliance", but do not meet the needs of a large number of users whose needs fall outside of traditional accessibility concerns. Older adults are an excellent example of users whose needs are often not considered during development.

A conference theater event will highlight computer use by persons with disabilities. Following up on that event, inclusive design in computer science education will be considered. The focus will be on populations that are often not considered in the design process.
Checklists for grading object-oriented CS1 programs
Authors: Sanders Kate , Thomas Lynda
Published: September 2007

In this paper, we begin by considering object-oriented programming concepts and typical novice misconceptions as identified in the literature. We then present the results of a close examination of student programs, in an objects-first CS1 course, in which we find concrete evidence of students learning these concepts while also displaying some of these misconceptions. This leads to the development of two checklists that educators can use when designing or grading student programs.
A classroom outsourcing experience for software engineering learning
Authors: Honig William L. , Prasad Tejasvini
Published: September 2007

Outsourcing of software development is a key part of globalization, oft misunderstood by computer science students, and possibly a cause of declining enrollments in the field. The authors developed and implemented an outsourcing experience for students in an advanced software engineering course. Student teams at two universities developed game playing programs and outsourced key parts of their systems to the other university. Results show students improved their understanding of outsourcing, developed better appreciation for the importance of software engineering techniques, and created ad hoc communication protocols between teams. The paper concludes with recommendations for expanding the approach used to other universities to create a more inclusive computer science and software engineering teaching environment.
Mental models and programming aptitude
Authors: Caspersen Michael E. , Larsen Kasper Dalgaard , Bennedsen Jens
Published: September 2007

Predicting the success of students participating in introductory programming courses has been an active research area for more than 25 years. Until recently, no variables or tests have had any significant predictive power. However, Dehnadi and Bornat claim to have found a simple test for programming aptitude to cleanly separate programming sheep from non-programming goats. We briefly present their theory and test instrument.

We have repeated their test in our local context in order to verify and perhaps generalise their findings, but we could not show that the test predicts students' success in our introductory program-ming course.

Based on this failure of the test instrument, we discuss various explanations for our differing results and suggest a research method from which it may be possible to generalise local results in this area. Furthermore, we discuss and criticize Dehnadi and Bornat's programming aptitude test and devise alternative test instruments.
Seven factors that influence ICT student achievement
Authors: Lang Catherine , McKay Judy , Lewis Sue
Published: September 2007

In the process of establishing an audit of student achievement by gender as part of a Women in IT project, seven factors were identified that affect student success. These seven factors had minimal effect when they occurred in isolation within a unit of study, but certain combinations of factors created a learning environment that was detrimental to all students, and in other instances a learning environment that was particularly unfavourable for female students. The impact of these findings has resulted in a set of recommendations to improve the teaching of IT in universities in general.
Problem solving and student performance in data structures and algorithms
Authors: Chinn Donald , Spencer Catherine , Martin Kristofer
Published: September 2007

Active and problem-based learning environments strive to improve students' problem solving skills. To better understand students' problem solving processes and thus guide the structure and development of such environments, we asked students to solve data structures and algorithms problems and to verbalize their thoughts as they solved them. In this paper, we discuss methodological issues associated with the analysis of their verbalizations. We then analyze and discuss the relationship between statistics that describe students' problem solving process and their performance in the course they were taking at the time, either the data structures or algorithms course.
IDEA
Authors: Adelmann Robert , Bischoff Tobias , Lauer Tobias
Published: September 2007

We present a Java-based framework for the easy and on-the-fly creation of algorithm animations. Animations are created by sketching both the objects that should be animated and operations that should be performed on them. The IDEA (Interactive Domain rEcognition and Animation) framework combines the recognition of drawn structures, the interaction with these structures and their animation in order to achieve an effortless and natural creation of animations. The framework itself supports the creation of animations in arbitrary domains through a dynamic plug-in architecture, where so-called domain modules encapsulate all domain-specific semantics. Its application and potential is outlined by the help of three prototypical domain modules for linear lists, Petri nets, and the game Connect-four.
How should inclusivity influence teaching of ict design?
Authors: Sloan David , Nelson Barbara , Sloan Martin
Published: September 2007

Accessibility and inclusive design is an important aspect of ICT education. This involves not only developing technical skills required to create accessible technology, but also fostering an awareness of the diversity amongst ICT users in terms of their capabilities and access environment. This session explores how CS learners can achieve not only skills in inclusive design but also acquire a more in-depth understanding of diversity and this influences the design of the ICT they produce.
Ideas for projects in undergraduate information assurance and security courses
Authors: Ghafarian Ahmad
Published: September 2007

In this work, we present some ideas for projects that can be used in undergraduate Information Assurance and Security (IAS) courses. The projects range from cryptanalysis of ciphertext, network security, security vulnerability analysis, and programming to demonstrate buffer overflow. The projects can be used in IAS courses such as cryptography, network security, and computer security. Alternatively, they can be used as separate modules in computer science courses such as operating systems, networking, and programming. Some of these projects have been piloted by the author and have achieved their objectives.
Understanding threads in an advanced java course
Authors: Benaya Tamar , Zur Ela
Published: September 2007

This poster describes difficultiesin understanding threads in an Advanced Java course given at the Computer Science department of the Open University of Israel (OUI). We present a typical question which focuseson several aspects of multi-threaded programming given in an exam. We discuss the students' answersand point to typical misunderstandings of the topic.
An investigation into the automated assessment of the design-code interface
Authors: Hayes Alan , Thomas Pete , Smith Neil , Waugh Kevin
Published: September 2007

In this paper, we present an investigation into the development of a framework for the automatic grading (marking) of student submitted course work. We discuss this framework, its structure and its subsystems. Our framework has been developed in the context of the student submission consisting of two components: a design (using the UML methodology) and source code (using the Java programming language). The focus of our framework is upon the consistency between the student code and design. We discuss its context and development and highlight how we can infer structure from the student submission and use this to inform the assessment process. We describe the approach we are currently undertaking to instantiate this framework and apply it to work submitted for assessment by undergraduate computing students.
New interactive tools for graph algorithms active learning
Authors: Sánchez-Torrubia M. Gloria , Torres-Blanc Carmen , Castellanos Juan
Published: September 2007

In this poster, some tools for graph algorithms active learning are presented. These tools pursue a new goal on computer assisted educational resources, so as to acting as authentic virtual trainers extending teacher's hand through the Web. In other words, they are on line self assessment tools that help students to execute the algorithms by themselves, correcting their mistakes and providing students with clues to find the right solution. Furthermore, the tools might be used as complementary material for bLearning.
'Touching the void'...
Authors: Dickinson Anne
Published: September 2007

The author's previous role within the Further Education sector, at North Warwickshire and Hinckley College, was to teach Information Technology (IT) to diverse groups of students who had varied abilities. This role was drawn upon in the author's current role when asked to tutor a student who had enrolled for a Degree in Business and IT at Coventry University.

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) and finding ways of working around them all. There were also occasions where it was necessary to create tactile diagrams [1] for the student. One of the diagrams produced was for critical path analysis. It was created to allow interactivity and to reflect a piece of specialist software that was used for helping students learn the topic. The materials used included using Euro cents, Wikki sticks [3] and string!.

A technician had been assigned to produce tactile diagrams for other modules. The technician realised that there were problems with some of the requests for tactile diagrams that were being received from some tutors. From discussions, it was clear that tutors were unaware of the issues involved with creating and using tactile diagrams. A void existed between their understanding from a visual context and how a tactile diagram worked. For many instances, creating a tactile diagram would not be appropriate as the complexity would be multiplied. A set of simple guidelines were produced that the technician could use as an aid to explaining issues to the tutors - 'touching the void' [5].

The tactile diagrams produced were using heated "swell paper" [2]. This meant that the diagram could be printed from an image on a computer. The resulting printout would be raised where lines were. However, it was discovered that this method gave some disappointing results. As there were no standards for tactile diagrams but some conventions and guidelines [4], a strategy was produced, from the experiences gained, to give optimum results when translating a diagram from the computer to the "swell paper".

This poster displays examples of tactile diagrams, guidelines given to tutors for requesting tactile diagrams and strategies for creating printable tactile diagrams.
A study of phylogenetic tools for genomic nomenclature data cleaning
Authors: Marra Jonathan D. , Herbert Katherine G. , Wang Jason T. L.
Published: September 2007

In this poster we propose a method for addressing the genomic nomenclature problem by using phylogenetic tools along with the BIO-AJAX data cleaning framework.
Evaluating the efficacy of a terrorism question/answer system
Authors: Schumaker Robert P. , Liu Ying , Ginsburg Mark , Chen Hsinchun
Published: September 2007

The TARA Project examined how a trio of modified chatterbots could be used to disseminate terrorism-related information to the general public.
The changing labyrinth of software pricing
Authors: Cusumano Michael A.
Published: September 2007

Exploring the malleable revenue pathways among the different varieties of pricing strategies.
Strangers, enemies, terms and taxonomies
Authors: Lister Raymond
Published: September 2007

It may be apocryphal, but I have been told that in some spoken languages the word for "stranger" is also the word for "enemy" -- to fail to make such a distinction must constrain one's behavior toward strangers. Likewise, our thinking on educational issues is constrained when we unaware of important distinctions. In the following paragraphs, I provide a potpourri of some my favorite terms and taxonomies that make important educational distinctions. I make no claim that these are the most useful distinctions. Instead, I merely seek to illustrate the importance of making distinctions.
We
can do interdisciplinarity
Authors: Kaczmarczyk Lisa
Published: September 2007

The year 2006 witnessed an unexpected milestone in my life: my first encounter with Poison Ivy. Not that I had never seen nor touched the infamous
Rhus radicans
before. Quite the contrary. A committed nature lover since birth, I have spent around four decades gloriously bushwhacking, tree hugging, dirt digging, bug chasing, rock clambering, and animal tracking. My body has suffered many indignities with aplomb. In each of these situations, I have watched with rapt attention the scientific processes at work: the sucking sounds as tweezers pull each cactus spine from my leg; the predictable trajectory of chigger blisters aiming towards their rendezvous on my toe with a fire-ant bite.
Students' understanding of computer science soft ideas
Authors: Stolin Yuila , Hazzan Orit
Published: September 2007

The article presents a research that focused on how the concept programming paradigm is understood in general, and on the understanding of the following three programming paradigms, in particular: functional, procedural, and object-oriented. The research population included seventeen prospective computer science teachers who were participating in a "Programming Paradigms" course. Research observations are organized within a framework that categorizes students' thinking about the concept of programming paradigm in three levels of abstraction.
Develop a compiler in Java for a compiler design course
Authors: Sattar Abdul , Lorenzen Torben
Published: September 2007

The authors' Compiler Design course at Bridgewater State College implemented a translator for a small language using Java. The project was broken into five assignments that included a language definition, extension of this language, a lexical analyzer, a recursive descent parser, and finally a code generator that generated Jasmin assembly language code for the JVM (Java Virtual Machine).
Laboratory redux
Authors: Dorin Philip M.
Published: September 2007

This article updates our earlier experiences with a Programming Laboratory. It appears between an introductory programming course and a two-semester sophomore sequence in data structures and algorithms. Although it was once organized around the notion of algorithm paradigms (with Ada as the implementation language), it has de-volved into a course that stresses fundamentals of programming (with Java as our programming language). Classes and objects, and the design and implementation of unit tests, are now considered to be part of the basic repertoire, and they receive significant attention in the new format.
A description and study of intermediate student programmer errors
Authors: Kopec Danny , Yarmish Gavriel , Cheung Patrick
Published: September 2007

To date there has been considerable investigation into the study of novice programmer errors. The research has analyzed both syntactic and semantic errors. However, the next level of programmers, who make more sophisticated errors, the internmediate level programmers, have been somewhat neglected. In this paper, we focus on the nature of the errors which intermediate level programmers make. The basis of our study is the semantic approach. Here, we the study problems which require more difficult program constructs such as nested loops, arrays, recursion, and functions.
Website error analysis of colleges and universities on Long Island in New York
Authors: Ebrahimi A. , Schweikert C. , Sayeed S. , Parham S. , Akibu H. , Saeed A. , Parris W.
Published: September 2007

Websites are an important means of communication for colleges and universities. Web-based presentations are replacing traditional ways of disseminating information. This study investigates the websites of 21 colleges and universities located on Long Island (Nassau, Suffolk) as well as five additional schools, four of which are Ivy League institutions. This research developed a technique of web site analysis known as 7X2 C's criteria, which are applied to seven separate layers of website application and development. The study concludes that the web sites of all the included institutions have errors across all the layers of the analysis to some degree that need to be corrected. Some of these errors are crucial, especially with regard to website search engines.
Dryad
Authors: Isard Michael , Budiu Mihai , Yu Yuan , Birrell Andrew , Fetterly Dennis
Published: September 2007

Dryad is a general-purpose distributed execution engine for coarse-grain data-parallel applications. A Dryad application combines computational "vertices" with communication "channels" to form a dataflow graph. Dryad runs the application by executing the vertices of this graph on a set of available computers, communicating as appropriate through flies, TCP pipes, and shared-memory FIFOs.

The vertices provided by the application developer are quite simple and are usually written as sequential programs with no thread creation or locking. Concurrency arises from Dryad scheduling vertices to run simultaneously on multiple computers, or on multiple CPU cores within a computer. The application can discover the size and placement of data at run time, and modify the graph as the computation progresses to make efficient use of the available resources.

Dryad is designed to scale from powerful multi-core single computers, through small clusters of computers, to data centers with thousands of computers. The Dryad execution engine handles all the difficult problems of creating a large distributed, concurrent application: scheduling the use of computers and their CPUs, recovering from communication or computer failures, and transporting data between vertices.
Melange
Authors: Madhavapeddy Anil , Ho Alex , Deegan Tim , Scott David , Sohan Ripduman
Published: September 2007

Most implementations of critical Internet protocols are written in type-unsafe languages such as C or C++ and are regularly vulnerable to serious security and reliability problems. Type-safe languages eliminate many errors but are not used to due to the perceived performance overheads.

We combine two techniques to eliminate this performance penalty in a practical fashion: strong static typing and generative meta-programming. Static typing eliminates run-time type information by checking safety at compile-time and minimises dynamic checks. Meta-programming uses a single specification to abstract the low-level code required to transmit and receive packets.

Our domain-specific language, MPL, describes Internet packet protocols and compiles into fast, zero-copy code for both parsing and creating these packets. MPL is designed for implementing quirky Internet protocols ranging from the low-level: Ethernet, IPv4, ICMP and TCP; to the complex application-level: SSH, DNS and BGP; and even file-system protocols such as 9P.

We report on fully-featured SSH and DNS servers constructed using MPL and our OCaml framework Melange, and measure greater throughput, lower latency, better flexibility and more succinct source code than their C equivalents OpenSSH and BIND. Our quantitative analysis shows that the benefits of MPL-generated code overcomes the additional overheads of automatic garbage collection and dynamic bounds checking. Qualitatively, the flexibility of our approach shows that dramatic optimisations are easily possible.
Sweeper
Authors: Tucek Joseph , Newsome James , Lu Shan , Huang Chengdu , Xanthos Spiros , Brumley David , Zhou Yuanyuan , Song Dawn
Published: September 2007

The vulnerabilities that plague computers cause endless grief to users. Slammer compromised millions of hosts in minutes; a hit-list worm would take under a second. Recently proposed techniques respond better than manual approaches, but require expensive instrumentation, which limits deployment. Although spreading "antibodies" (e.g. signatures) ameliorates this limitation, hosts depending on antibodies are defenseless until inoculation; to the fastest hit-list worms this delay is crucial. Additionally, most recently proposed techniques cannot provide recovery to provide continuous service after an attack.

We propose a novel solution called Sweeper that provides both
fast and accurate
post-attack analysis and
efficient
recovery
with low normal execution overhead
. Sweeper in-novatively combines several techniques: (1) Sweeper uses
lightweight
monitoring techniques to detect a wide array of suspicious requests, providing a first level of defense. (2) By cleverly leveraging lightweight checkpointing, Sweeper postpones heavyweight monitoring until absolutely necessary --- after an attack is detected. Sweeper rolls back and re-executes multiple times to dynamically apply heavyweight analysis techniques via dynamic binary instrumentation. Since only the execution involved in the attack is analyzed, the analysis is efficient, yet thorough. (3) Based on the analysis results, Sweeper automatically generates low-overhead antibodies to prevent future attacks of the same vulnerability. (4) Finally, Sweeper again re-executes to perform fast recovery for continuous service.

We implement Sweeper in a real system. Our experimental results with three real-world servers and four real security vulnerabilities show that Sweeper can detect an attack and generate antibodies in under 60 milliseconds. Our results also show that Sweeper imposes under 1% overhead during normal execution, clearly suitable for widespread production deployment (especially since Sweeper also allows partial deployment). Finally, we analytically show that, for a fast hit-list worm otherwise capable of infecting all vulnerable hosts in under a second, Sweeper contains the extent of infection to under 5%.
hFS
Authors: Zhang Zhihui , Ghose Kanad
Published: September 2007

Two oft-cited file systems, the Fast File System (FFS) and the Log-Structured File System (LFS), adopt two sharply different update strategies---
update-in-place
and
update-out-of-place
. This paper introduces the design and implementation of a hybrid file system called hFS, which combines the strengths of FFS and LFS while avoiding their weaknesses. This is accomplished by distributing file system data into
two partitions
based on their size and type. In hFS, data blocks of large regular files are stored in a data partition arranged in a FFS-like fashion, while metadata and small files are stored in a separate log partition organized in the spirit of LFS but
without incurring any cleaning overhead
. This segregation makes it possible to use more appropriate layouts for different data than would otherwise be possible. In particular, hFS has the ability to perform
clustered I/O
on
all
kinds of data---including small files, metadata, and large files. We have implemented a prototype of hFS on FreeBSD and have compared its performance against three file systems, including FFS with Soft Updates, a port of NetBSD's LFS, and our lightweight journaling file system called yFS. Results on a number of benchmarks show that hFS has excellent small file and metadata performance. For example, hFS beats FFS with Soft Updates in the range from 53% to 63% in the PostMark benchmark.
Competitive prefetching for concurrent sequential I/O
Authors: Li Chuanpeng , Shen Kai , Papathanasiou Athanasios E.
Published: September 2007

During concurrent I/O workloads, sequential access to one I/O stream can be interrupted by accesses to other streams in the system. Frequent switching between multiple sequential I/O streams may severely affect I/O efficiency due to long disk seek and rotational delays of disk-based storage devices. Aggressive prefetching can improve the granularity of sequential data access in such cases, but it comes with a higher risk of retrieving unneeded data. This paper proposes a
competitive
prefetching strategy that controls the prefetching depth so that the overhead of disk I/O switch and unnecessary prefetching are balanced. The proposed strategy does not require
a-priori
information on the data access pattern, and achieves at least half the performance (in terms of I/O throughput) of the optimal offline policy. We also provide analysis on the optimality of our competitiveness result and extend the competitiveness result to capture prefetching in the case of random-access workloads.

We have implemented the proposed competitive prefetching policy in Linux 2.6.10 and evaluated its performance on both standalone disks and a disk array using a variety of workloads (including two common file utilities, Linux kernel compilation, the TPC-H benchmark, the Apache web server, and index searching). Compared to the original Linux kernel, our competitive prefetching system improves performance by up to 53%. At the same time, it trails the performance of an oracle prefetching strategy by no more than 42%.
Fine grained kernel logging with KLogger
Authors: Etsion Yoav , Tsafrir Dan , Kirkpatrick Scott , Feitelson Dror G.
Published: September 2007

Understanding the detailed behavior of an operating system is crucial for making informed design decisions. But such an understanding is very hard to achieve, due to the increasing complexity of such systems and the fact that they are implemented and maintained by large and diverse groups of developers. Tools like KLogger --- presented in this paper --- can help by enabling fine-grained logging of system events and the sharing of a logging infrastructure between multiple developers and researchers, facilitating a methodology where design evaluation can be an integral part of kernel development. We demonstrate the need for such methodology by a host of case studies, using KLogger to better understand various subsystems in the Linux kernel, and pinpointing overheads and problems therein.
Multimedia retrieval at INEX 2006
Authors: Westerveld Thijs , van Zwol Roelof
Published: September 2007

Structured document retrieval allows for the retrieval of document fragments, i.e. XML elements, containing relevant information. The main INEX Ad Hoc track focuses on text-based XML element retrieval. Although text is dominantly present in most XML document collections, other types of media can also be found. Existing research on multimedia information retrieval has shown that it is far from trivial to determine the combined relevance of a document that contains several multimedia objects. The objective of the INEX multimedia track is to exploit the XML structure that provides a logical level at which multimedia objects are connected, to improve the retrieval performance of an XML-driven multimedia information retrieval system.
Nearest-neighbor-preserving embeddings
Authors: Indyk Piotr , Naor Assaf
Published: September 2007

In this article we introduce the notion of nearest-neighbor-preserving embeddings. These are randomized embeddings between two metric spaces which preserve the (approximate) nearest-neighbors. We give two examples of such embeddings for Euclidean metrics with low “intrinsic” dimension. Combining the embeddings with known data structures yields the best-known approximate nearest-neighbor data structures for such metrics.
Virtual private caches
Authors: Nesbit Kyle J. , Laudon James , Smith James E.
Published: September 2007

Virtual Private Machines (VPM) provide a framework for Quality of Service (QoS) in CMP-based computer systems. VPMs incorporate microarchitecture mechanisms that allow shares of hardware resources to be allocated to executing threads, thus providing applications with an upper bound on execution time regardless of other thread activity. Virtual Private Caches (VPCs) are an important element of VPMs. VPC hardware consists of two major components: the VPC Arbiter, which manages shared cache bandwidth, and the VPC Capacity Manager, which manages the cache storage. Both the VPC Arbiter and VPC Capacity Manager provide minimum service guarantees that, when combined, achieve QoS for the cache subsystem. Simulation-based evaluation shows that conventional cache bandwidth management policies allow concurrently executing threads to affect each other significantly in an uncontrollable manner. The evaluation targets cache bandwidth because the effects of cache capacity sharing have been studied elsewhere. In contrast with the conventional policies, the VPC Arbiter meets its QoS performance objectives on all workloads studied and over a range of allocated bandwidth levels. The VPC Arbiter’s fairness policy, which distributes leftover bandwidth, mitigates the effects of cache preemption latencies, thus ensuring threads a high-degree of performance isolation. Furthermore, the VPC Arbiter eliminates negative bandwidth interference which can improve aggregate throughput and resource utilization.
Performance pathologies in hardware transactional memory
Authors: Bobba Jayaram , Moore Kevin E. , Volos Haris , Yen Luke , Hill Mark D. , Swift Michael M. , Wood David A.
Published: September 2007

Hardware Transactional Memory (HTM) systems reflect choices from three key design dimensions: conflict detection, version management, and conflict resolution. Previously proposed HTMs represent three points in this design space: lazy conflict detection, lazy version management, committer wins (LL); eager conflict detection, lazy version management, requester wins (EL); and eager conflict detection, eager version management, and requester stalls with conservative deadlock avoidance (EE). To isolate the effects of these high-level design decisions, we develop a common framework that abstracts away differences in cache write policies, interconnects, and ISA to compare these three design points. Not surprisingly, the relative performance of these systems depends on the workload. Under light transactional loads they perform similarly, but under heavy loads they differ by up to 80%. None of the systems performs best on all of our benchmarks. We identify seven
performance pathologies
-interactions between workload and system that degrade performance-as the root cause of many performance differences: FriendlyFire, StarvingWriter, SerializedCommit, FutileStall, StarvingElder, RestartConvoy, and DuelingUpgrades. We discuss when and on which systems these pathologies can occur and show that they actually manifest within TM workloads. The insight provided by these pathologies motivated four enhanced systems that often significantly reduce transactional memory overhead. Importantly, by avoiding transaction pathologies, each enhanced system performs well across our suite of benchmarks.
Carbon
Authors: Kumar Sanjeev , Hughes Christopher J. , Nguyen Anthony
Published: September 2007

Chip multiprocessors (CMPs) are now commonplace, and the number of cores on a CMP is likely to grow steadily. However, in order to harness the additional compute resources of a CMP, applications must expose their thread-level parallelism to the hardware. One common approach to doing this is to decompose a program into parallel "tasks" and allow an underlying software layer to schedule these tasks to different threads. Software task scheduling can provide good parallel performance as long as tasks are large compared to the software overheads.

We examine a set of applications from an important emerging domain: Recognition, Mining, and Synthesis (RMS). Many RMS applications are compute-intensive and have abundant thread-level parallelism, and are therefore good targets for running on a CMP. However, a significant number have small tasks for which software task schedulers achieve only limited parallel speedups.

We propose Carbon, a hardware technique to accelerate dynamic task scheduling on scalable CMPs. Carbon has relatively simple hardware, most of which can be placed far from the cores. We compare Carbon to some highly tuned software task schedulers for a set of RMS benchmarks with small tasks. Carbon delivers significant performance improvements over the best software scheduler: on average for 64 cores, 68% faster on a set of loop-parallel benchmarks, and 109% faster on aset of task-parallel benchmarks.
Interconnect design considerations for large NUCA caches
Authors: Muralimanohar Naveen , Balasubramonian Rajeev
Published: September 2007

The ever increasing sizes of on-chip caches and the growing domination of wire delay necessitate significant changes to cache hierarchy design methodologies. Many recent proposals advocate splitting the cache into a large number of banks and employing a network-on-chip (NoC) to allow fast access to nearby banks (referred to as Non-Uniform Cache Architectures--NUCA). Most studies on NUCA organizations have assumed a generic NoC and focused on logical policies for cache block placement, movement, and search. Since wire/router delay and power are major limiting factors in modern processors, this work focuses on interconnect design and its influence on NUCA performance and power. We extend the widely-used CACTI cache modeling tool to take network design parameters into account. With these overheads appropriately accounted for, the optimal cache organization is typically very different from that assumed in prior NUCA studies. To alleviate the interconnect delay bottleneck, we propose novel cache access optimizations that introduce heterogeneity within the inter-bank network. The careful consideration of interconnect choices for a large cache results in a 51% performance improvement over a baseline generic NoC and the introduction of heterogeneity within the network yields an additional 11-15% performance improvement.