bluuebunny/crossref_metadata_2025 huggingface dataset:
Static analysis of multi-staged programs via unstaging translation
Authors: Choi Wontae , Aktemur Baris , Yi Kwangkeun , Tatsuta Makoto
Published: January 2011

Static analysis of multi-staged programs is challenging because the basic assumption of conventional static analysis no longer holds: the program text itself is no longer a fixed static entity, but rather a dynamically constructed value. This article presents a semantic-preserving translation of multi-staged call-by-value programs into unstaged programs and a static analysis framework based on this translation. The translation is semantic-preserving in that every small-step reduction of a multi-staged program is simulated by the evaluation of its unstaged version. Thanks to this translation we can analyze multi-staged programs with existing static analysis techniques that have been developed for conventional unstaged programs: we first apply the unstaging translation, then we apply conventional static analysis to the unstaged version, and finally we cast the analysis results back in terms of the original staged program. Our translation handles staging constructs that have been evolved to be useful in practice (typified in Lisp's quasi-quotation): open code as values, unrestricted operations on references and intentional variable-capturing substitutions. This article omits references for which we refer the reader to our companion technical report.
Static analysis of interrupt-driven programs synchronized via the priority ceiling protocol
Authors: Schwarz Martin D. , Seidl Helmut , Vojdani Vesal , Lammich Peter , Müller-Olm Markus
Published: January 2011

We consider programs for embedded real-time systems which use priority-driven preemptive scheduling with task priorities adjusted dynamically according to the immediate ceiling priority protocol. For these programs, we provide static analyses for detecting data races between tasks running at different priorities as well as methods to guarantee transactional execution of procedures. Beyond that, we demonstrate how general techniques for value analyses can be adapted to this setting by developing a precise analysis of affine equalities.
A kripke logical relation between ML and assembly
Authors: Hur Chung-Kil , Dreyer Derek
Published: January 2011

There has recently been great progress in proving the correctness of compilers for increasingly realistic languages with increasingly realistic runtime systems. Most work on this problem has focused on proving the correctness of a particular compiler, leaving open the question of how to verify the correctness of assembly code that is hand-optimized or linked together from the output of multiple compilers. This has led Benton and other researchers to propose more abstract, compositional notions of when a low-level program correctly realizes a high-level one. However, the state of the art in so-called "compositional compiler correctness" has only considered relatively simple high-level and low-level languages.

In this paper, we propose a novel, extensional, compiler-independent notion of equivalence between high-level programs in an expressive, impure ML-like λ-calculus and low-level programs in an (only slightly) idealized assembly language. We define this equivalence by means of a biorthogonal, step-indexed, Kripke logical relation, which enables us to reason quite flexibly about assembly code that uses local state in a different manner than the high-level code it implements (
e.g.
self-modifying code). In contrast to prior work, we factor our relation in a symmetric, language-generic fashion, which helps to simplify and clarify the formal presentation, and we also show how to account for the presence of a garbage collector. Our approach relies on recent developments in Kripke logical relations for ML-like languages, in particular the idea of possible worlds as state transition systems.
A typed store-passing translation for general references
Authors: Pottier François
Published: January 2011

We present a store-passing translation of System
F
with general references into an extension of System
F
ω
with certain well-behaved recursive kinds. This seems to be the first type-preserving store-passing translation for general references. It can be viewed as a purely syntactic account of a possible worlds model.
Blame for all
Authors: Ahmed Amal , Findler Robert Bruce , Siek Jeremy G. , Wadler Philip
Published: January 2011

Several programming languages are beginning to integrate static and dynamic typing, including Racket (formerly PLT Scheme), Perl 6, and C# 4.0 and the research languages Sage (Gronski, Knowles, Tomb, Freund, and Flanagan, 2006) and Thorn (Wrigstad, Eugster, Field, Nystrom, and Vitek, 2009). However, an important open question remains, which is how to add parametric polymorphism to languages that combine static and dynamic typing. We present a system that permits a value of dynamic type to be cast to a polymorphic type and vice versa, with relational parametricity enforced by a kind of dynamic sealing along the lines proposed by Matthews and Ahmed (2008) and Neis, Dreyer, and Rossberg (2009). Our system includes a notion of blame, which allows us to show that when casting between a more-precise type and a less-precise type, any cast failures are due to the less-precisely-typed portion of the program. We also show that a cast from a subtype to its supertype cannot fail.
Correct blame for contracts
Authors: Dimoulas Christos , Findler Robert Bruce , Flanagan Cormac , Felleisen Matthias
Published: January 2011

Behavioral software contracts supplement interface information with logical assertions. A rigorous enforcement of contracts provides useful feedback to developers if it signals contract violations as soon as they occur and if it assigns blame to violators with preciseexplanations. Correct blame assignment gets programmers started with the debugging process and can significantly decrease the time needed to discover and fix bugs.

Sadly the literature on contracts lacks a framework for making statements about the correctness of blame assignment and for validating such statements. This paper fills the gap and uses the framework to demonstrate how one of the proposed semantics for higher-order contracts satisfies this criteria and another semantics occasionally assigns blame to the wrong module.

Concretely, the paper applies the framework to the
lax
enforcement of dependent higher-order contracts and the
picky
one. A higher-order dependent contract specifies constraints for the domain and range of higher-order functions and also relates arguments and results in auxiliary assertions. The picky semantics ensures that the use of arguments in the auxiliary assertion satisfies the domain contracts and the lax one does not. While the picky semantics discovers more contract violations than the lax one, it occasionally blames the wrong module. Hence the paper also introduces a third semantics, dubbed
indy
, which fixes the problems of the picky semantics without giving up its advantages.
Generative type abstraction and type-level computation
Authors: Weirich Stephanie , Vytiniotis Dimitrios , Peyton Jones Simon , Zdancewic Steve
Published: January 2011

Modular languages support generative type abstraction, ensuring that an abstract type is distinct from its representation, except inside the implementation where the two are synonymous. We show that this well-established feature is in tension with the non-parametric features of newer type systems, such as indexed type families and GADTs. In this paper we solve the problem by using kinds to distinguish between parametric and non-parametric contexts. The result is directly applicable to Haskell, which is rapidly developing support for type-level computation, but the same issues should arise whenever generativity and non-parametric features are combined.
The design of kodu
Authors: MacLaurin Matthew B.
Published: January 2011

Kodu is a relatively new programming language designed specifically for young children to learn through independent exploration. Kodu seeks to lower the barrier to entry for new programmers by presenting a radically simplified programming model which nevertheless has significant expressive power. Kodu is integrated in a real-time 3D gaming environment and is designed to compete with modern console games in terms of intuitive user interface and graphical production values. In this paper we will review key tradeoffs made in the design of the programming language and illustrate how it is one of very few languages designed using user interface design principles and methodologies, to the extent that the blend of subjective and objective factors considered in the language design have succeeded in presenting a model of programming which is uniquely approachable and creatively empowering for non-technical users.
A separation logic for refining concurrent objects
Authors: Turon Aaron Joseph , Wand Mitchell
Published: January 2011

Fine-grained concurrent data structures are crucial for gaining performance from multiprocessing, but their design is a subtle art. Recent literature has made large strides in verifying these data structures, using either atomicity refinement or separation logic with rely-guarantee reasoning. In this paper we show how the ownership discipline of separation logic can be used to enable atomicity refinement, and we develop a new rely-guarantee method that is localized to the definition of a data structure. We present the first semantics of separation logic that is sensitive to atomicity, and show how to control this sensitivity through ownership. The result is a logic that enables compositional reasoning about atomicity and interference, even for programs that use fine-grained synchronization and dynamic memory allocation.
Expressive modular fine-grained concurrency specification
Authors: Jacobs Bart , Piessens Frank
Published: January 2011

Compared to coarse-grained external synchronization of operations on data structures shared between concurrent threads, fine-grained, internal synchronization can offer stronger progress guarantees and better performance. However, fully specifying operations that perform internal synchronization modularly is a hard, open problem. The state of the art approaches, based on linearizability or on concurrent abstract predicates, have important limitations on the expressiveness of specifications. Linearizability does not support ownership transfer, and the concurrent abstract predicates-based specification approach requires hardcoding a particular usage protocol. In this paper, we propose a novel approach that lifts these limitations and enables fully general specification of fine-grained concurrent data structures. The basic idea is that clients pass the ghost code required to instantiate an operation's specification for a specific client scenario into the operation in a simple form of higher-order programming.

We machine-checked the theory of the paper using the Coq proof assistant. Furthermore, we implemented the approach in our program verifier VeriFast and used it to verify two challenging fine-grained concurrent data structures from the literature: a multiple-compare-and-swap algorithm and a lock-coupling list.
The tree width of auxiliary storage
Authors: Madhusudan P. , Parlato Gennaro
Published: January 2011

We propose a generalization of results on the decidability of emptiness for several restricted classes of sequential and distributed automata with auxiliary storage (stacks, queues) that have recently been proved. Our generalization relies on reducing emptiness of these automata to finite-state
graph automata
(without storage) restricted to monadic second-order (MSO) definable graphs of bounded tree-width, where the graph structure encodes the mechanism provided by the auxiliary storage. Our results outline a uniform mechanism to derive emptiness algorithms for automata, explaining and simplifying several existing results, as well as proving new decidability results.
Automating string processing in spreadsheets using input-output examples
Authors: Gulwani Sumit
Published: January 2011

We describe the design of a string programming/expression language that supports restricted forms of regular expressions, conditionals and loops. The language is expressive enough to represent a wide variety of string manipulation tasks that end-users struggle with. We describe an algorithm based on several novel concepts for synthesizing a desired program in this language from input-output examples. The synthesis algorithm is very efficient taking a fraction of a second for various benchmark examples. The synthesis algorithm is interactive and has several desirable features: it can rank multiple solutions and has fast convergence, it can detect noise in the user input, and it supports an active interaction model wherein the user is prompted to provide outputs on inputs that may have multiple computational interpretations.

The algorithm has been implemented as an interactive add-in for Microsoft Excel spreadsheet system. The prototype tool has met the golden test - it has synthesized part of itself, and has been used to solve problems beyond author's imagination.
Predicate abstraction and refinement for verifying multi-threaded programs
Authors: Gupta Ashutosh , Popeea Corneliu , Rybalchenko Andrey
Published: January 2011

Automated verification of multi-threaded programs requires explicit identification of the interplay between interacting threads, so-called environment transitions, to enable scalable, compositional reasoning. Once the environment transitions are identified, we can prove program properties by considering each program thread in isolation, as the environment transitions keep track of the interleaving with other threads. Finding adequate environment transitions that are sufficiently precise to yield conclusive results and yet do not overwhelm the verifier with unnecessary details about the interleaving with other threads is a major challenge. In this paper we propose a method for safety verification of multi-threaded programs that applies (transition) predicate abstraction-based discovery of environment transitions, exposing a minimal amount of information about the thread interleaving. The crux of our method is an abstraction refinement procedure that uses recursion-free Horn clauses to declaratively state abstraction refinement queries. Then, the queries are resolved by a corresponding constraint solving algorithm. We present preliminary experimental results for mutual exclusion protocols and multi-threaded device drivers.
Geometry of synthesis III
Authors: Ghica Dan R. , Smith Alex
Published: January 2011

Geometry of Synthesis
is a technique for compiling higher-level programming languages into digital circuits via their game semantic model. Ghica (2007) first presented the key idea, then Ghica and Smith (2010) gave a provably correct compiler into asynchronous circuits for Syntactic Control of Interference (SCI), an affine-typed version of Reynolds's Idealized Algol. Affine typing has the dual benefits of ruling out race conditions through the type system and having a finite-state game-semantic model for any term, which leads to a natural circuit representation and simpler correctness proofs. In this paper we go beyond SCI to full Idealized Algol, enhanced with shared-memory concurrency and semaphores.

Compiling ICA proceeds in three stages. First, an intermediate type system called Syntactic Control of Concurrency (SCC), is used to statically determine "concurrency bounds" on all identifiers in the program. Then, a program transformation called
serialization
is applied to the program to translate it into an equivalent SCC program in which all concurrency bounds are set to the unit. Finally, the resulting program can be then compiled into asynchronous circuits using a slightly enhanced version of the GoS II compiler, which can handle assignable variables used in non-sequential contexts.
Dynamic multirole session types
Authors: Deniélou Pierre-Malo , Yoshida Nobuko
Published: January 2011

Multiparty session types enforce structured safe communications between several participants, as long as their number is fixed when the session starts. In order to handle common distributed interaction patterns such as peer-to-peer protocols or cloud algorithms, we propose a new role-based multiparty session type theory where roles are defined as classes of local behaviours that an arbitrary number of participants can dynamically join and leave. We offer programmers a polling operation that gives access to the current set of a role's participants in order to fork processes. Our type system with universal types for polling can handle this dynamism and retain type safety. A multiparty locking mechanism is introduced to provide communication safety, but also to ensure a stronger progress property for joining participants that has never been guaranteed in previous systems. Finally, we present some implementation mechanisms used in our prototype extension of ML.
Bisimulation for quantum processes
Authors: Feng Yuan , Duan Runyao , Ying Mingsheng
Published: January 2011

Quantum cryptographic systems have been commercially available, with a striking advantage over classical systems that their security and ability to detect the presence of eavesdropping are provable based on the principles of quantum mechanics. On the other hand, quantum protocol designers may commit much more faults than classical protocol designers since human intuition is much better adapted to the classical world than the quantum world. To offer formal techniques for modeling and verification of quantum protocols, several quantum extensions of process algebra have been proposed. One of the most serious issues in quantum process algebra is to discover a quantum generalization of the notion of bisimulation, which lies in a central position in process algebra, preserved by parallel composition in the presence of quantum entanglement, which has no counterpart in classical computation. Quite a few versions of bisimulation have been defined for quantum processes in the literature, but in the best case they are only proved to be preserved by parallel composition of purely quantum processes where no classical communications are involved.

Many quantum cryptographic protocols, however, employ the LOCC (Local Operations and Classical Communications) scheme, where classical communications must be explicitly specified. So, a notion of bisimulation preserved by parallel composition in the circumstance of both classical and quantum communications is crucial for process algebra approach to verification of quantum cryptographic protocols. In this paper we introduce a novel notion of bisimulation for quantum processes and prove that it is congruent with respect to various process algebra combinators including parallel composition even when both classical and quantum communications are present. We also establish some basic algebraic laws for this bisimulation. In particular, we prove uniqueness of the solutions to recursive equations of quantum processes, which provides a powerful proof technique for verifying complex quantum protocols.
Loop transformations
Authors: Pouchet Louis-Noël , Bondhugula Uday , Bastoul Cédric , Cohen Albert , Ramanujam J. , Sadayappan P. , Vasilache Nicolas
Published: January 2011

High-level loop transformations are a key instrument in mapping computational kernels to effectively exploit the resources in modern processor architectures. Nevertheless, selecting required compositions of loop transformations to achieve this remains a significantly challenging task; current compilers may be off by orders of magnitude in performance compared to hand-optimized programs. To address this fundamental challenge, we first present a convex characterization of all distinct, semantics-preserving, multidimensional affine transformations. We then bring together algebraic, algorithmic, and performance analysis results to design a tractable optimization algorithm over this highly expressive space. Our framework has been implemented and validated experimentally on a representative set of benchmarks running on state-of-the-art multi-core platforms.
Resourceable, retargetable, modular instruction selection using a machine-independent, type-based tiling of low-level intermediate code
Authors: Ramsey Norman , Dias João
Published: January 2011

We present a novel variation on the standard technique of selecting instructions by tiling an intermediate-code tree. Typical compilers use a different set of tiles for every target machine. By analyzing a formal model of machine-level computation, we have developed a single set of tiles that is
machine-independent
while retaining the expressive power of machine code. Using this tileset, we reduce the number of tilers required from one per machine to one per architectural family (e.g., register architecture or stack architecture). Because the tiler is the part of the instruction selector that is most difficult to reason about, our technique makes it possible to retarget an instruction selector with significantly less effort than standard techniques. Retargeting effort is further reduced by applying an earlier result which generates the machine-dependent implementation of our tileset automatically from a declarative description of instructions' semantics. Our design has the additional benefit of enabling modular reasoning about three aspects of code generation that are not typically separated: the semantics of the compiler's intermediate representation, the semantics of the target instruction set, and the techniques needed to generate
good
target code.
Verifying higher-order functional programs with pattern-matching algebraic data types
Authors: Ong C.-H. Luke , Ramsay Steven J.
Published: January 2011

Type-based model checking algorithms for higher-order recursion schemes have recently emerged as a promising approach to the verification of functional programs. We introduce
pattern-matching recursion schemes
(PMRS) as an accurate model of computation for functional programs that manipulate algebraic data-types. PMRS are a natural extension of higher-order recursion schemes that incorporate pattern-matching in the defining rules.

This paper is concerned with the following (undecidable) verification problem: given a correctness property φ, a functional program ℘ (
qua
PMRS) and a regular input set ℑ, does every term that is reachable from ℑ under rewriting by ℘ satisfy φ? To solve the PMRS verification problem, we present a sound
semi-algorithm
which is based on model-checking and counterexample guided abstraction refinement. Given a no-instance of the verification problem, the method is guaranteed to terminate.

From an order-
n
PMRS and an input set generated by a regular tree grammar, our method constructs an order-
n weak
PMRS which over-approximates
only
the first-order pattern-matching behaviour, whilst remaining completely faithful to the higher-order control flow. Using a variation of Kobayashi's type-based approach, we show that the (trivial automaton) model-checking problem for weak PMRS is decidable. When a violation of the property is detected in the abstraction which does not correspond to a violation in the model, the abstraction is automatically refined by `unfolding' the pattern-matching rules in the program to give successively more and more accurate weak PMRS models.
A framework for characterizing the wireless and mobile network continuum
Authors: Chen Yang , Borrel Vincent , Ammar Mostafa , Zegura Ellen
Published: January 2011

The vast majority of research in wireless and mobile (WAM) networking falls in the MANET (Mobile Ad Hoc Network) category, where end-to-end paths are the norm. More recently, research has focused on a different Disruption Tolerant Network (DTN) paradigm, where end-to-end paths are the exception and intermediate nodes may store data while waiting for transfer opportunities towards the destination. Protocols developed for MANETs are generally not appropriate for DTNs and vice versa, since the connectivity assumptions are so different. We make the simple but powerful observation that MANETs and DTNs fit into a continuum that generalizes these two previously distinct categories. In this paper, building on this observation, we develop a WAM continuum framework that goes further to scope the entire space of Wireless and Mobile networks so that a network can be characterized by its position in this continuum. Certain network equivalence classes can be defined over subsets of this WAM continuum. We instantiate our framework that allows network connectivity classification and show how that classification relates to routing. We illustrate our approach by applying it to networks described by traces and by mobility models. We also outline how our framework can be used to guide network design and operation.
NeTraMark
Authors: Lee Suchul , Kim Hyunchul , Barman Dhiman , Lee Sungryoul , Kim Chong-kwon , Kwon Ted , Choi Yanghee
Published: January 2011

Recent research on Internet traffic classification has produced a number of approaches for distinguishing types of traffic. However, a rigorous comparison of such proposed algorithms still remains a challenge, since every proposal considers a different benchmark for its experimental evaluation. A lack of clear consensus on an objective and cientific way for comparing results has made researchers uncertain of fundamental as well as relative contributions and limitations of each proposal. In response to the growing necessity for an objective method of comparing traffic classifiers and to shed light on scientifically grounded traffic classification research, we introduce an Internet traffic classification benchmark tool, NeTraMark. Based on six design guidelines (Comparability, Reproducibility, Efficiency, Extensibility, Synergy, and Flexibility/Ease-of-use), NeTraMark is the first Internet traffic lassification benchmark where eleven different state-of-the-art traffic classifiers are integrated. NeTraMark allows researchers and practitioners to easily extend it with new classification algorithms and compare them with other built-in classifiers, in terms of three categories of performance metrics: per-whole-trace flow accuracy, per-application flow accuracy, and computational performance.
Explaining packet delays under virtualization
Authors: Whiteaker Jon , Schneider Fabian , Teixeira Renata
Published: January 2011

This paper performs controlled experiments with two popular virtualization techniques, Linux-VServer and Xen, to examine the effects of virtualization on packet sending and receiving delays. Using a controlled setting allows us to independently investigate the influence on delay measurements when competing virtual machines (VMs) perform tasks that consume CPU, memory, I/O, hard disk, and network bandwidth. Our results indicate that heavy network usage from competing VMs can introduce delays as high as 100 ms to round-trip times. Furthermore, virtualization adds most of this delay when sending packets, whereas packet reception introduces little extra delay. Based on our findings, we discuss guidelines and propose a feedback mechanism to avoid measurement bias under virtualization.
Dynamically scaling applications in the cloud
Authors: Vaquero Luis M. , Rodero-Merino Luis , Buyya Rajkumar
Published: January 2011

Scalability is said to be one of the major advantages brought by the cloud paradigm and, more specifically, the one that makes it different to an "advanced outsourcing" solution. However, there are some important pending issues before making the dreamed automated scaling for applications come true. In this paper, the most notable initiatives towards whole application scalability in cloud environments are presented. We present relevant efforts at the edge of state of the art technology, providing an encompassing overview of the trends they each follow. We also highlight pending challenges that will likely be addressed in new research efforts and present an ideal scalable cloud system.
ExtremeCom
Authors: Lindgren Anders , Hui Pan
Published: January 2011

Research on networks for challenged environments has become a major research area recently. There is however a lack of true understanding among networking researchers about what such environments really are like. In this paper we give an introduction to the ExtremeCom series of workshops that were created to overcome this limitation. We will discuss the motivation behind why the workshop series was created, give some summaries of the two workshops that have been held, and discuss the lessons that we have learned from them.
Instrumenting home networks
Authors: Calvert Kenneth L. , Edwards W. Keith , Feamster Nick , Grinter Rebecca E. , Deng Ye , Zhou Xuzi
Published: January 2011

In managing and troubleshooting home networks, one of the challenges is in knowing what is actually happening. Availability of a record of events that occurred on the home network
before
trouble appeared would go a long way toward addressing that challenge. In this position/work-in-progress paper, we consider requirements for a general-purpose logging facility for home networks. Such a facility, if properly designed, would potentially have other uses. We describe several such uses and discuss requirements to be considered in the design of a logging platform that would be widely supported and accepted. We also report on our initial deployment of such a facility.
HTTP in the home
Authors: Erman Jeffrey , Gerber Alexandre , Sen Subhabrata
Published: January 2011

HTTP (Hypertext Transport Protocol) was originally primarily used for human-initiated client-server communications launched from web browsers, traditional computers and laptops. However, today it has become the protocol of choice for a bewildering range of applications from a wide array of emerging devices like smart TVs and gaming consoles. This paper presents an initial study characterizing the non-traditional sources of HTTP traffic such as consumer devices and automated updates in the overall HTTP traffic for residential Internet users. Among our findings,13% of all HTTP traffic in terms of bytes is due to non-traditional sources, with 5% being from consumer devices such as WiFi enabled smartphones and 8% generated from automated software updates and background processes. Our findings show that 11% of all HTTP requests are caused by communications with advertising servers from as many as 190 countries worldwide, suggesting the widespread prevalence of such activities. Overall, our findings start to answer questions about what is the state of traffic generated in these smart homes.
Running servers around zero degrees
Authors: Pervilä Mikko , Kangasharju Jussi
Published: January 2011

Data centers are a major consumer of electricity and a significant fraction of their energy use is devoted to cooling the data center. Recent prototype deployments have investigated the possibility of using outside air for cooling and have shown large potential savings in energy consumption. In this paper, we push this idea to the extreme, by running servers outside in Finnish winter. Our results show that commercial, off-the-shelf computer equipment can tolerate extreme conditions such as outside air temperatures below --20 C and still function correctly over extended periods of time. Our experiment improves upon the other recent results by confirming their findings and extending them to cover a wider range of intake air temperatures and humidity. This paper presents our experimentation methodology and setup, and our main findings and observations.
NapSAC
Authors: Krioukov Andrew , Mohan Prashanth , Alspaugh Sara , Keys Laura , Culler David , Katz Randy
Published: January 2011

Energy consumption is a major and costly problem in data centers. A large fraction of this energy goes to powering idle machines that are not doing any useful work. We identify two causes of this inefficiency: low server utilization and a lack of power-proportionality. To address this problem we present a design for an power-proportional cluster consisting of a power-aware cluster manager and a set of heterogeneous machines. Our design makes use of currently available energy-efficient hardware, mechanisms for transitioning in and out of low-power sleep states, and dynamic provisioning and scheduling to continually adjust to workload and minimize power consumption. With our design we are able to reduce energy consumption while maintaining acceptable response times for a web service workload based on Wikipedia. With our dynamic provisioning algorithms we demonstrate via simulation a 63% savings in power usage in a typically provisioned datacenter where all machines are left on and awake at all times. Our results show that we are able to achieve close to 90% of the savings a theoretically optimal provisioning scheme would achieve. We have also built a prototype cluster which runs Wikipedia to demonstrate the use of our design in a real environment.
How internet concepts and technologies can help green and smarten the electrical grid
Authors: Keshav Srinivasan , Rosenberg Catherine
Published: January 2011

Several powerful forces are gathering to make fundamental and irrevocable changes to the century-old grid. The next-generation grid, often called the 'smart grid,' will feature distributed energy production, vastly more storage, tens of millions of stochastic renewable-energy sources, and the use of communication technologies both to allow precise matching of supply to demand and to incentivize appropriate consumer behaviour. These changes will have the effect of reducing energy waste and reducing the carbon footprint of the grid, making it 'smarter' and 'greener.' In this position paper, we discuss how the concepts and techniques pioneered by the Internet, the fruit of four decades of research in this area, are directly applicable to the design of a smart, green grid. This is because both the Internet and the electrical grid are designed to meet fundamental needs, for information and for energy, respectively, by connecting geographically dispersed suppliers with geographically dispersed consumers. Keeping this and other similarities (and fundamental differences, as well) in mind, we propose several specific areas where Internet concepts and technologies can contribute to the development of a smart, green grid. We also describe some areas where the Internet operations can be improved based on the experience gained in the electrical grid. We hope that our work will initiate a dialogue between the Internet and the smart grid communities.
MPAP
Authors: He Yong , Fang Ji , Zhang Jiansong , Shen Haichen , Tan Kun , Zhang Yongguang
Published: January 2011

This demonstration shows a novel virtualization architecture, called
Multi-Protocol Access Point
(MPAP), which exploits the software radio technology to virtualize multiple heterogenous wireless standards on single radio hardware. The basic idea is to deploy a wide-band radio front-end to receive radio signals from all wireless standards sharing the same spectrum band, and use separate software base-bands to demodulate information stream for each wireless standard. Based on software radio, MPAP consolidates multiple wireless devices into single hardware platform, allowing them to share the common general-purpose computing resource. Different software base-bands can easily communicate and coordinate via a software coordinator and coexist better with one another. As one example, we demonstrate to use non-contiguous OFDM in 802.11g PHY to avoid the mutual interference with narrow-band ZigBee communication.
A temporal coding hardware implementation for spiking neural networks
Authors: Nuño-Maganda Marco , Torres-Huitzil Cesar
Published: January 2011

Spiking Neural Networks (SNNs) models have been explored in recent years due to its biological plausibility where temporal coding plays an important role. Biological arguments and computational experiments suggest than some perceptual tasks (vision and olfaction for instance) are well performed by these models. Moreover, some other applications such as machine learning might be benefited from this approach. However, efficient simulation and implementation of SNNs still remain an open challenge. There are several issues that must be addressed, being one of them the temporal coding of real-value data itself. In order to study the possibilities of embedded real-time implementations of large scale SNNs, we have first chosen to implement a well-known coding scheme based on Gaussian Receptive Fields (GRFs) to map real-value data into spike trains. This paper proposes a configurable parallel FPGA based accelerator for GRF-based temporal coding. The proposed architecture of the hardware implementation is described in detail and implementation results, both performance and resource utilization, when mapped to a Virtex-II Pro FPGA device are reported.
Implementation and evaluation of an arithmetic pipeline on FLOPS-2D: multi-FPGA system
Authors: Morisita Hirokazu , Inakagata Kenta , Osana Yasunori , Fujita Naoyuki , Amano Hideharu
Published: January 2011

UPACS (Unified Platform for Aerospace Computational Simulation) is one of the practical CFD (Computational Fluid Dynamics) packages supporting various selectability. A custom machine for efficient execution of MUSCL; a core functions of UPACS is implemented on FLOPS-2D (Flexibly Linkable Object for Programmable System); multi-FPGA reconfigurable system. The deep and complicated pipeline structure generated from MUSCL dataflow is divided and optimized into two FPGA boards by using a tuning tool called RER. With optimization of the order of operations and pipeline structure, about 60% utilization of the pipeline is achieved even by using serial links between two boards. The execution time is 6.16-23.19 times faster than that of the software on 2.66 GHz Intel Core 2 Duo processor.
An FPGA-based fast classifier with high generalization property
Authors: Horita Tadayoshi , Takanami Itsuo
Published: January 2011

This paper proposes a scheme to implement classifiers with high generalization properties on FPGAs. The classifiers consist of only combinational logic circuits, which are based on a simple concept, and the VHDL source files which describe the classifiers are generated by a C-language function, tuning VHDL notations for adders in them to reduce both its hardware size and computation time. Simulation results based on a character recognition are shown in terms of generalization property, hardware size, computation time, and electricity consumption.
Binary acceleration using coarse-grained reconfigurable architecture
Authors: Paek Jong Kyung , Choi Kiyoung , Lee Jongeun
Published: January 2011

Coarse-grained reconfigurable architectures (CGRAs) have been well-researched and shown to be particularly effective in acceleration of data-intensive applications. However, practical difficulties in application mapping have hindered their widespread adoption. Typically, an application must be modified manually or by using special compilers and design tools in order to fully exploit the architecture. This incurs considerable design costs to the application developer and reduces software portability. In this paper, we propose a framework for automatic transformation of an application at binary-level, with which the user can execute an arbitrary application on the CGRA. Our approach analyzes the binary code and determines which portions of the program to accelerate, maps them to the reconfigurable array, then modifies the binary code appropriately to run on the CGRA. We describe the overall process of our framework, and present solutions to several problems that arise from such an approach. Results from our preliminary experiments show that we are able to achieve speedup of up to 14.8.
Programming framework for clusters with heterogeneous accelerators
Authors: Tsoi Kuen Hung , Tse Anson H.T. , Pietzuch Peter , Luk Wayne
Published: January 2011

We describe a programming framework for high performance clusters with various hardware accelerators. In this framework, users can utilize the available heterogeneous resources productively and efficiently. The distributed application is highly modularized to support dynamic system configuration with changing types and number of the accelerators. Multiple layers of communication interface are introduced to reduce the overhead in both control messages and data transfers. Parallelism can be achieved by controlling the accelerators in various schemes through scheduling extension. The framework has been used to support physics simulation and financial application development. We achieve significant performance improvement on a 16-node cluster with FPGA and GPU accelerators.
Multipliers for floating-point double precision and beyond on FPGAs
Authors: Banescu Sebastian , de Dinechin Florent , Pasca Bogdan , Tudoran Radu
Published: January 2011

The implementation of high-precision floating-point applications on reconfigurable hardware requires large multipliers. Full multipliers are the core of floating-point multipliers. Truncated multipliers, trading resources for a well-controlled accuracy degradation, are useful building blocks in situations where a full multiplier is not needed.

This work studies the automated generation of such multipliers using the embedded multipliers and adders present in the DSP blocks of current FPGAs. The optimization of such multipliers is expressed as a tiling problem, where a tile represents a hardware multiplier, and super-tiles represent combinations of several hardware multipliers and adders, making efficient use of the DSP internal resources. This tiling technique is shown to adapt to full or truncated multipliers. It addresses arbitrary precisions including single, double but also the quadruple precision introduced by the IEEE-754-2008 standard and currently unsupported by processor hardware. An open-source implementation is provided in the FloPoCo project.
Dynamic power reduction of FPGA-based reconfigurable computers using precomputation
Authors: Tsang Chi-Chiu , So Hayden Kwok-Hay
Published: January 2011

This paper examines the effectiveness of employing precomputation techniques to reduce power consumption of field configurable computing systems. Multiplier is modified with precomputation techniques and are implemented using commercial off-the-shelf FPGAs. Precomputation techniques reduce dynamic power consumption of a module by eliminating unnecessary signal switching activities in inactive portions of the modules. Experiments have shown that up to 52% of logic and signal power consumption can be reduced in multiplier module. Furthermore, when compared to ASIC implementations, FPGA implementations of precomputation modules have the advantage of lower area overhead as most of them can be implemented using originally unoccupied related FPGA resources. Finally, it was found that the effectiveness of precomputation depends heavily on the input data statistics. It is expected that compilers for future reconfigurable computers may take full advantage of such power saving techniques by optimizing the architecture according to data input statistics.
Conceptualizing privacy
Authors: Gerber Benjamin
Published: January 2011

I often lead discussions and give presentations where I need to get the audience in the mindset to start thinking about privacy in a way to which they could personally relate, understand others' privacy expectations, and discover for themselves that privacy is about more than just technical security controls for personally identifiable information (PII). Below are an approach and an exercise I took my audience through in a few presentations last year; they both have been well received and I think others might find them useful.
Biometrics
Authors: Gibbs Martin D.
Published: January 2011

Odor detection and identification by machines is currently being done to evaluate perfumes, wine, olive, oil, and even find people buried in rubble. Extending body odor detection to authentication may seem far-fetched and unrealistic. Yet such an application is plausible, given that like a fingerprint or iris, the human body odor is unique. Although such technology still has strides to make before being applicable as either a stand-alone or supplemental technology to existing biometric tools, it still warrants research, especially in how the technology is perceived. Numerous studies have addressed the public perception of biometric technologies, although odor scanning is one that has been under-addressed. This exploratory study addresses perceptions and attitudes of odor scanning and recommends directions for future research and practice. This study has found that odor scanning is little understood, and its benefit to security and privacy are perceived as low. Should body odor scanning develop into a viable method of biometric authentication, issues of perception and acceptance will need further attention by both research and practice.
Electronic media, creativity and plagiarism
Authors: Imran Naveed
Published: January 2011

This article provides an introduction to plagiarism and the numerous negative aspects associated with it. Some examples from history have also been provided along with their outcomes. There are different types of plagiarism with varying legal and social aspects. The taxonomy of plagiarism is built by classifying it, with respect to the method involved in plagiarism, the form in which it happens or the intention of the plagiarist. The strategies suggested in the literature to avoid plagiarism are organized into individual and organizational levels. Individuals can adopt strategies to build habits of avoiding plagiarism and focus on their original and innovative way of thinking. Similarly, institutions can make policies to cope with plagiarism and hence maintain their reputation. In this paper, the focus is not on mentioning the plagiarism detection methods; rather we believe that building awareness in the people about plagiarism outcomes is more important than teaching them about the different methodologies used for detection. Some students avoid plagiarism detection as if playing a game and it can be only avoided by educating them in ethics.
The 2010 Schubmehl-Prein Essay Competition
Authors: Bowyer Kevin W.
Published: January 2011

The 2010 competition was the sixth year of the Schubmehl-Prein contest for the Best Essay on Social Impact of Computing. The topic for this year turned was one that turned out to be in the news even more than anticipated --
What Should Individual Privacy Rights Be With Respect To Services Such As "Street View?
The topic was originally envisioned primarily as one that would lead students to consider the different concepts of privacy that various countries have enforced in dealing with Street View. But the anticipated scope expanded when Street View hit the news for having intercepted and saved some unsecured wireless traffic during data acquisition. In any case, this year's topic was clearly one that students were able to have fun working on.
Puzzling over privacy
Authors: Oetter Tess
Published: January 2011

In this essay, I focus on the controversy over privacy regarding Google Street View, a website created in the fall of 2008. I also discuss privacy and its role in technology, enumerating several ways in which privacy policy in these situations should be changed for the better.
Individual privacy rights with respect to services such as Google Street View
Authors: Thornton James
Published: January 2011

For a person to squeeze his fingers is legal. For a person to face towards another person is legal. For a person to sight down the barrel of a gun is legal. Yet, for that same person to do all three of these things at once is very illegal. Although Google Street View, or GSV for short, and similar services may be comprised of previously accepted functions---operation of an automobile, photography, internet publishing, mapmaking, advertising, etc.---the whole of a thing is far different from the constituent pieces with which it is comprised. The context, accessibility, and ease of manipulation pertaining to the data presented by Google are radically altered by the organization that is fundamental to the product. Google Street View must be evaluated as an experimental and almost completely unprecedented foray into a still developing area of technology.