bluuebunny/crossref_metadata_2025 huggingface dataset:
Postplacement rewiring by exhaustive search for functional symmetries
Authors: Chang Kai-Hui , Markov Igor L. , Bertacco Valeria
Published: September 2007

We propose two new algorithms for rewiring: a postplacement optimization that reconnects pins of a given netlist without changing the logic function and gate locations. In the first algorithm, we extract small subcircuits consisting of several gates from the design and reconnect pins according to the symmetries of the subcircuits. To enhance the power of symmetry detection, we also propose a graph-based symmetry detector that can identify permutational and phase-shift symmetries on multiple input and output wires, as well as hybrid symmetries, creating abundant opportunities for rewiring. Our second algorithm, called long-range rewiring, is based on reconnecting equivalent pins and can augment the first approach for further optimization. We apply our techniques for wirelength optimization and observe that they provide wirelength reduction comparable to that achieved by detailed placement.
EWD
Authors: Mathaikutty Deepak , Patel Hiren , Shukla Sandeep , Jantsch Axel
Published: September 2007

We present the EWD design environment and methodology, a modeling and simulation framework suited for complex and heterogeneous embedded systems with varying degrees of expressibility and modeling fidelity. This environment promotes the use of multiple models of computation (MoCs) to support heterogeneity and metamodeling for conformance tests of syntactic and static semantics during the process of modeling. Therefore, EWD is a multiple MoC modeling and simulation framework that ensures conformance of the MoC formalisms during model construction using a metamodeling approach. In addition, EWD provides a suite of translation tools that generate executable models for two simulation frameworks to demonstrate its language-independent modeling framework. The EWD methodology uses the Generic Modeling Environment for customization of the MoC-specific modeling syntax into a visual representation. To embed the execution semantics of the MoCs into the models, we have built parsing and translation tools that leverage an XML-based interoperability language. This interoperability language is then translated into executable Standard ML or Haskell models that can also be analyzed by existing simulation frameworks such as SML-Sys or ForSyDe. In summary, EWD is a metamodeling driven multitarget design environment with multi-MoC modeling capability.
Binary synthesis
Authors: Stitt Greg , Vahid Frank
Published: September 2007

Recent high-level synthesis approaches and C-based hardware description languages attempt to improve the hardware design process by allowing developers to capture desired hardware functionality in a well-known high-level source language. However, these approaches have yet to achieve wide commercial success due in part to the difficulty of incorporating such approaches into software tool flows. The requirement of using a specific language, compiler, or development environment may cause many software developers to resist such approaches due to the difficulty and possible instability of changing well-established robust tool flows. Thus, in the past several years, synthesis from binaries has been introduced, both in research and in commercial tools, as a means of better integrating with tool flows by supporting all high-level languages and software compilers. Binary synthesis can be more easily integrated into a software development tool-flow by only requiring an additional backend tool, and it even enables completely transparent dynamic translation of executing binaries to configurable hardware circuits. In this article, we survey the key technologies underlying the important emerging field of binary synthesis. We compare binary synthesis to several related areas of research, and we then describe the key technologies required for effective binary synthesis: decompilation techniques necessary for binary synthesis to achieve results competitive with source-level synthesis, hardware/software partitioning methods necessary to find critical binary regions suitable for synthesis, synthesis methods for converting regions to custom circuits, and binary update methods that enable replacement of critical binary regions by circuits.
Speedups in embedded systems with a high-performance coprocessor datapath
Authors: Galanis Michalis D. , Dimitroulakos Gregory , Tragoudas Spyros , Goutis Costas E.
Published: September 2007

This article presents the speedups achieved in a generic single-chip microprocessor system by employing a high-performance datapath. The datapath acts as a coprocessor that accelerates computational-intensive kernel sections thereby increasing the overall performance. We have previously introduced the datapath which is composed of Flexible Computational Components (FCCs). These components can realize any two-level template of primitive operations. The automated coprocessor synthesis method from high-level software description and its integration to a design flow for executing applications on the system is presented. For evaluating the effectiveness of our coprocessor approach, analytical study in respect to the type of the custom datapath and to the microprocessor architecture is performed. The overall application speedups of several real-life applications relative to the software execution on the microprocessor are estimated using the design flow. These speedups range from 1.75 to 5.84, with an average value of 3.04, while the overhead in circuit area is small. The design flow achieved the acceleration of the applications near to theoretical speedup bounds. A comparison with another high-performance datapath showed that the proposed coprocessor achieves smaller area-time products by an average of 23% for the generated datapaths. Additionally, the FCC coprocessor achieves better performance in accelerating kernels relative to software-programmable DSP cores.
Event propagation for accurate circuit delay calculation using SAT
Authors: Roy Suchismita , Chakrabarti P. P. , Dasgupta Pallab
Published: September 2007

A SAT-based modeling for event propagation in gate-level digital circuits, which is used for accurate calculation of critical delay in combinational and sequential circuits, is presented in this article. The accuracy of the critical delay estimation process depends on the accuracy with which the circuit in operation is modeled. A high level of precision in the modeling of the internal events in a circuit for the sake of greater accuracy causes a combinatorial blowup in the size of the problem, resulting in a scalability bottleneck for which most existing techniques effect a trade-off by restricting themselves to less precise models. SAT based techniques have a good track record in efficiency and scalability when the problem sizes become too large for most other methods. This article proposes a SAT-based technique for symbolic event propagation within a circuit which facilitates the estimation of the critical delay of circuits with a greater degree of accuracy, while at the same time scaling efficiently to large circuits. We report very encouraging results on the ISCAS85 and ISCAS89 benchmark circuits using the proposed technique.
The spin-wave nanoscale reconfigurable mesh and the labeling problem
Authors: Eshaghian-Wilner Mary M. , Khitun Alex , Navab Shiva , Wang Kang L.
Published: September 2007

In this article, we present a nanoscale reconfigurable mesh which is interconnected by ferromagnetic spin-wave buses. In this architecture, unlike the traditional spin-based nano structures which transmit charge, waves are transmitted. As a result, the power consumption of the proposed modules can be low. This reconfigurable mesh, while requiring the same number of switches and buses as the standard reconfigurable mesh, is capable of simultaneously transmitting N waves on each of the spin-wave buses. Because of this highly parallel feature, very fast and fault-tolerant algorithms can be designed. To illustrate the superior performance of the proposed spin-wave reconfigurable mesh, we present three fast labeling algorithms.
Design for dependability in emerging technologies
Authors: Prodan Lucian , Udrescu Mihai , Boncalo Oana , Vladutiu Mircea
Published: September 2007

As current microelectronics will reach their physical limits within the foreseeable future, emerging technologies may offer a solution for maintaining the trends to increase computing performance. Biologically-inspired and quantum computing represent two emerging technology vectors for novel computing architectures within nanoelectronics. However, potential benefits will come at the cost of increased device sensitivity to the surrounding environment. This article provides a dependability perspective over these technologies from a designer's standpoint. Maintaining or increasing the dependability of unconventional computational processes is discussed in two different contexts, a bio-inspired computing architecture (the
Embryonics
project) and a quantum computational architecture (the
QUERIST
project).
Evolving dependability
Authors: Tyrrell Andy M. , Greensted Andrew J.
Published: September 2007

Evolvable hardware offers much for the future of complex systems design. Evolutionary techniques not only have the potential for larger solution space coverage, but when implemented on hardware, also allow system designs to adapt to changes in the environment, including failures in system components. This article reviews a number of novel techniques, all based in the field of bio-inspired systems, that provide varying degrees of dependability over and above standard designs. In particular, three different techniques are considered: using FPGAs and ideas from developmental biology to create designs that possess emergent fault-tolerant properties, using FPGAs and continuous evolution to circumvent faults as and when they occur, and, finally, we consider a novel ASIC designed and built with bio-inspired systems in mind.
Evolutionary functional recovery in virtual reconfigurable circuits
Authors: Sekanina Lukáš
Published: September 2007

A virtual reconfigurable circuit (VRC) is a domain-specific reconfigurable device developed using an ordinary FPGA in order to easily implement evolvable hardware applications. While a fast partial runtime reconfiguration and application-specific programmable elements represent the main advantages of VRC, the main disadvantage of the VRC is the area consumed. This study describes experiments conducted to estimate how the use of VRC influences the dependability of FPGA-based evolvable systems. It is shown that these systems are not as sensitive to faults as their area-demanding implementations might suggest. An evolutionary algorithm is utilized to design fault tolerant circuits as well as to perform an automatic functional recovery when faults are detected in the configuration memory of the FPGA. All the experiments are performed on models of reconfigurable devices.
Self-replicating hardware for reliability
Authors: Tempesti Gianluca , Mange Daniel , Mudry Pierre-Andre , Rossier Joël , Stauffer Andre
Published: September 2007

The multicellular structure of biological organisms and the interpretation in each of their cells of a chemical program (the DNA string or
genome
) is the source of inspiration for the Embryonics (embryonic electronics) project, whose final objective is the design of highly robust integrated circuits, endowed with properties usually associated with the living world: self-repair and self-replication. In this article, we provide an overview of our latest research in the domain of the self-replication of processing elements within a programmable logic substrate, a key prerequisite for achieving system-level fault tolerance in our bio-inspired approach.
Evaluating HDR rendering algorithms
Authors: Kuang Jiangtao , Yamaguchi Hiroshi , Liu Changmeng , Johnson Garrett M. , Fairchild Mark D.
Published: September 2007

A series of three experiments has been performed to test both the preference and accuracy of high dynamic-range (HDR) rendering algorithms in digital photography application. The goal was to develop a methodology for testing a wide variety of previously published tone-mapping algorithms for overall preference and rendering accuracy. A number of algorithms were chosen and evaluated first in a paired-comparison experiment for overall image preference. A rating-scale experiment was then designed for further investigation of individual image attributes that make up overall image preference. This was designed to identify the correlations between image attributes and the overall preference results obtained from the first experiments. In a third experiment, three real-world scenes with a diversity of dynamic range and spatial configuration were designed and captured to evaluate seven HDR rendering algorithms for both of their preference and accuracy performance by comparing the appearance of the physical scenes and the corresponding tone-mapped images directly. In this series of experiments, a modified Durand and Dorsey's bilateral filter technique consistently performed well for both preference and accuracy, suggesting that it is a good candidate for a common algorithm that could be included in future HDR algorithm testing evaluations. The results of these experiments provide insight for understanding of perceptual HDR image rendering and should aid in design strategies for spatial processing and tone mapping. The results indicate ways to improve and design more robust rendering algorithms for general HDR scenes in the future. Moreover, the purpose of this research was not simply to find out the “best” algorithms, but rather to find a more general psychophysical experiment based methodology to evaluate HDR image-rendering algorithms. This paper provides an overview of the many issues involved in an experimental framework that can be used for these evaluations.
Discrimination and identification of finger joint-angle position using active motion
Authors: Tan Hong Z. , Srinivasan Mandayam A. , Reed Charlotte M. , Durlach Nathaniel I.
Published: September 2007

The authors report six experiments on the human ability to discriminate and identify finger joint-angle positions using active motion. The PIP (proximal interphalangeal) joint of the index finger was examined in Exps. 1--3 and the MCP (metacarpophalangeal) joint in Exps. 4--6. In Exp. 1, the just noticeable difference (JND) of PIP joint-angle position was measured when the MCP joint was either fully extended or halfway bent. In Exp. 2, the JND of PIP joint-angle position as a function of PIP joint-angle reference position was measured when the PIP joint was almost fully extended, halfway bent, or almost fully flexed. In Exp. 3, the information transfer of PIP joint-angle position was estimated with the MCP joint in a fully extended position. In Exps. 4--6, the JND and the information transfer of MCP joint-angle position were studied with a similar experimental design. The results show that the JNDs of the PIP joint-angle position were roughly constant (2.5°−2.7°) independent of the PIP joint-angle reference position or the MCP joint-angle position used (Exps. 1 and 2). The JNDs of the MCP joint-angle position, however, increased with the flexion of both the PIP and MCP joints and ranged from 1.7° to 2.7° (Exps. 4 and 5). The information transfer of the PIP and MCP joint-angle position were similar, indicating 3--4 perfectly identifiable joint-angle positions for both joints (Exps. 3 and 6). The results provide the basic data needed for estimating, for example, the resolution of fingertip position during active free motion. They are compared to the results from previous studies on joint position, length, and thickness perception.
Modeling embodied visual behaviors
Authors: Sprague Nathan , Ballard Dana , Robinson Al
Published: September 2007

To make progess in understanding human visuomotor behavior, we will need to understand its basic components at an abstract level. One way to achieve such an understanding would be to create a model of a human that has a sufficient amount of complexity so as to be capable of generating such behaviors. Recent technological advances have been made that allow progress to be made in this direction. Graphics models that simulate extensive human capabilities can be used as platforms from which to develop synthetic models of visuomotor behavior. Currently, such models can capture only a small portion of a full behavioral repertoire, but for the behaviors that they do model, they can describe complete visuomotor subsystems at a useful level of detail. The value in doing so is that the body's elaborate visuomotor structures greatly simplify the specification of the abstract behaviors that guide them. The net result is that, essentially, one is faced with proposing an embodied “operating system” model for picking the right set of abstract behaviors at each instant. This paper outlines one such model. A centerpiece of the model uses vision to aid the behavior that has the most to gain from taking environmental measurements. Preliminary tests of the model against human performance in realistic VR environments show that main features of the model show up in human behavior.
Functional similarities in spatial representations between real and virtual environments
Authors: Williams Betsy , Narasimham Gayathri , Westerman Claire , Rieser John , Bodenheimer Bobby
Published: September 2007

This paper presents results that demonstrate functional similarities in subjects' access to spatial knowledge (or
spatial representation
) between real and virtual environments. Such representations are important components of the transfer of reasoning ability and knowledge between these two environments. In particular, we present two experiments aimed at investigating similarities in spatial knowledge derived from exploring on foot both physical environments and virtual environments presented through a head-mounted display. In the first experiment, subjects were asked to learn the locations of target objects in the real or virtual environment and then rotate the perspective by either physically locomoting to a new facing direction or imagining moving. The latencies and errors were generally worse after imagining locomoting and for greater degrees of rotation in perspective; they did not differ significantly across knowledge derived from exploring the physical versus virtual environments. In the second experiment, subjects were asked to imagine simple rotations versus simple translations in perspective. The errors and latencies indicated that the to-be-imagined disparity was linearly related after learning the physical and virtual environment. These results demonstrate functional similarities in access to knowledge of new perspective when it is learned by exploring physical environments and virtual renderings of the same environment.
Development and evaluation of a thermal display for material identification and discrimination
Authors: Ho Hsin-Ni , Jones Lynette A.
Published: September 2007

The objective of this study was to develop and evaluate a thermal display that assists in object identification in virtual environments by simulating the thermal cues associated with making contact with materials with different thermal properties. The thermal display was developed based on a semi-infinite body model. Three experiments were conducted to evaluate the performance of the display. The first experiment compared the ability of subjects' to identify various materials, which were presented physically or simulated with the thermal display. The second experiment examined the capacity of subjects to discriminate between a real and simulated material based on thermal cues. In the third experiment, the changes in skin temperature that occurred when making contact with real and simulated materials were measured to evaluate how these compare to theoretical predictions. The results indicated that there was no significant difference in material identification and discrimination when subjects were presented with real or simulated materials. The changes in skin temperature were comparable for real and simulated materials and were related to the contact coefficient of the material palpated, consistent with the semi-infinite body model. These findings suggest that a thermal display is capable of facilitating object recognition when visual cues are limited.
Provably secure authenticated group Diffie-Hellman key exchange
Authors: Bresson Emmanuel , Chevassut Olivier , Pointcheval David
Published: September 2007

Authenticated key-exchange protocols allow two participants
A
and
B
, communicating over a public network and each holding an authentication means to exchange a shared secret value. Methods designed to deal with this cryptographic problem ensure
A
(resp.
B
) that no other participants aside from
B
(resp.
A
) can learn any information about the agreed value and often also ensure
A
and
B
that their respective partner has actually computed this value. A natural extension to this cryptographic method is to consider a pool of participants exchanging a shared secret value and to provide a formal treatment for it. Starting from the famous two-party Diffie--Hellman (DH) key-exchange protocol and from its authenticated variants, security experts have extended it to the multiparty setting for over a decade and, in the past few years, completed a formal analysis in the framework of modern cryptography. The present paper synthesizes this body of work on the provably-secure authenticated group DH key exchange.
On interdomain routing security and pretty secure BGP (psBGP)
Authors: Oorschot P.C. van , Wan Tao , Kranakis Evangelos
Published: September 2007

It is well known that the Border Gateway Protocol (BGP), the IETF standard interdomain routing protocol, is vulnerable to a variety of attacks, and that a single misconfigured or malicious BGP speaker could result in large-scale service disruption. In this paper, we present
Pretty Secure BGP (psBGP)
---a proposal for securing BGP, including an architectural overview, design details for significant aspects, and preliminary security and operational analysis. psBGP differs from other security proposals (e.g., S-BGP and soBGP) in that it makes use of a single-level PKI for AS number authentication, a decentralized trust model for verifying the propriety of IP prefix origin, and a rating-based stepwise approach for AS_PATH (integrity) verification. psBGP trades off the strong security guarantees of S-BGP for presumed-simpler operation, e.g., using a PKI with a simple structure, with a small number of certificate types, and of manageable size. psBGP is designed to successfully defend against various (nonmalicious and malicious) threats from uncoordinated BGP speakers, and to be incrementally deployed with incremental benefits.
PP-trust-X
Authors: Squicciarini A. , Bertino E. , Ferrari Elena , Paci F. , Thuraisingham B.
Published: September 2007

Trust negotiation is a promising approach for establishing trust in open systems, in which sensitive interactions may often occur between entities with no prior knowledge of each other. Although, to date several trust negotiation systems have been proposed, none of them fully address the problem of privacy preservation. Today, privacy is one of the major concerns of users when exchanging information through the Web and thus we believe that trust negotiation systems must effectively address privacy issues in order to be widely applicable. For these reasons, in this paper, we investigate privacy in the context of trust negotiations. We propose a set of privacy-preserving features for inclusion in any trust negotiation system, such as the support for the P3P standard, as well as a number of innovative features, such as a novel format for encoding digital credentials specifically designed for preserving privacy. Further, we present a variety of interoperable strategies to carry on the negotiation with the aim of improving both privacy and efficiency.
Interleaved hop-by-hop authentication against false data injection attacks in sensor networks
Authors: Zhu Sencun , Setia Sanjeev , Jajodia Sushil , Ning Peng
Published: September 2007

Sensor networks are often deployed in unattended environments, thus leaving these networks vulnerable to
false data injection attacks
in which an adversary injects false data into the network with the goal of deceiving the base station or depleting the resources of the relaying nodes. Standard authentication mechanisms cannot prevent this attack if the adversary has compromised one or a small number of sensor nodes. We present three interleaved hop-by-hop authentication schemes that guarantee that the base station can detect injected false data
immediately
when no more than
t
nodes are compromised, where
t
is a system design parameter. Moreover, these schemes enable an intermediate forwarding node to detect and discard false data packets as early as possible. Our performance analysis shows that our scheme is efficient with respect to the security it provides, and it also allows a tradeoff between security and performance. A prototype implementation of our scheme indicates that our scheme is practical and can be deployed on the current generation of sensor nodes.
Collaborative broadcasting and compression in cluster-based wireless sensor networks
Authors: Hoang Anh Tuan , Motani Mehul
Published: September 2007

Achieving energy efficiency to prolong the network lifetime is an important design criterion for wireless sensor networks. In this article, we propose a novel approach that exploits the broadcast nature of the wireless medium for energy conservation in spatially correlated wireless sensor networks. Since wireless transmission is inherently broadcast, when one sensor node transmits, other nodes in its coverage area can receive the transmitted data. When data collected by different sensors are correlated, each sensor can utilize the data it overhears from other sensors to compress its own data and conserve energy in its own transmissions. We apply this idea to a class of cluster-based wireless sensor networks in which each sensing node transmits collected data directly to its cluster head using time division multiple access (TDMA). We formulate the problem in which sensors in each cluster collaborate their transmitting, receiving, and compressing activities to optimize their lifetimes. We show that this lifetime optimization problem can be solved by a sequence of linear programming problems. We also propose a heuristic scheme which has low complexity and achieves near optimal performance. Important characteristics of wireless sensor networks such as node startup cost and packet loss due to transmission errors are also considered. Numerical results show that by exploiting the broadcast nature of the wireless medium, our control schemes achieve significant improvement in the sensors' lifetimes.
Extrapolation errors in linear model trees
Authors: Loh Wei-Yin , Chen Chien-Wei , Zheng Wei
Published: September 2007

Prediction errors from a linear model tend to be larger when extrapolation is involved, particularly when the model is wrong. This article considers the problem of extrapolation and interpolation errors when a linear model tree is used for prediction. It proposes several ways to curtail the size of the errors, and uses a large collection of real datasets to demonstrate that the solutions are effective in reducing the average mean squared prediction error. The article also provides a proof that, if a linear model is correct, the proposed solutions have no undesirable effects as the training sample size tends to infinity.
Mining periodic patterns with gap requirement from sequences
Authors: Zhang Minghua , Kao Ben , Cheung David W. , Yip Kevin Y.
Published: September 2007

We study a problem of mining frequently occurring periodic patterns with a gap requirement from sequences. Given a character sequenceSof lengthLand a patternPof lengthl, we considerPa frequently occurring pattern inSif the probability ofobservingPgiven a randomly picked length-lsubsequence ofSexceeds a certain threshold. In many applications, particularly those related to bioinformatics, interesting patterns areperiodicwith agap requirement. That is to say, the characters inPshould match subsequences ofSin such a way that the matching characters inSare separated by gaps of more or less the same size. We show the complexity of the mining problem and discuss why traditional mining algorithms are computationally infeasible. We propose practical algorithms for solving the problem and study their characteristics. We also present a case study in which we apply our algorithms on some DNA sequences. We discuss some interesting patterns obtained from the case study.
Twain
Authors: Huang Jen-Wei , Dai Bi-Ru , Chen Ming-Syan
Published: September 2007

We investigate the general model of mining associations in a temporal database, where the exhibition periods of items are allowed to be different from one to another. The database is divided into partitions according to the time granularity imposed. Such temporal association rules allow us to observe short-term but interesting patterns that are absent when the whole range of the database is evaluated altogether. Prior work may omit some temporal association rules and thus have limited practicability. To remedy this and to give more precise frequent exhibition periods of frequent temporal itemsets, we devise an efficient algorithm
Twain
(standing for
TWo end AssocIation miNer
.)
Twain
not only generates frequent patterns with more precise frequent exhibition periods, but also discovers more interesting frequent patterns.
Twain
employs Start time and End time of each item to provide precise frequent exhibition period while progressively handling itemsets from one partition to another. Along with one scan of the database,
Twain
can generate frequent 2-itemsets directly according to the cumulative filtering threshold. Then,
Twain
adopts the scan reduction technique to generate all frequent
k
-itemsets (
k
> 2) from the generated frequent 2-itemsets. Theoretical properties of
Twain
are derived as well in this article. The experimental results show that
Twain
outperforms the prior works in the quality of frequent patterns, execution time, I/O cost, CPU overhead and scalability.
EC practitioners
Authors: Hornby Gregory S. , Yu Tina
Published: September 2007

The field of Evolutionary Computation (EC) has been around for several decades [2, 3], and in recent years there has been an explosion not only in the different types of biologically inspired algorithms, but also in the number of practitioners in the field. A critical part of this growth and development of the EC field has been the technology transfer of EC from academia to industry and the successful application of EC techniques to real-world problems. To assist in the continued technology transfer of EC techniques from academia to industry we conducted a survey of EC practitioners working in both academia and industry and in this article we summarize some of our findings.
Interactive music composition with the CFE framework
Authors: Chen Ying-ping
Published: September 2007

This article presents an interactive music composition system which utilizes the black-box optimization model of evolutionary computation. The core CFE framework---Composition, Feedback, and Evolution---is presented and described. The music composition system produces short, manageable pieces of music by interacting with users. The essential features of the system include the capability of creating customized pieces of music based on the user preference and the facilities specifically designed for generating a large amount of music. Finally, several pieces of music composed by the described system are demonstrated as showcases. This work shows that it is feasible and promising for computers to automatically compose customized or personalized music.
Can the PC go green?
Authors: Weiss Aaron
Published: September 2007

The usual depictions of modern life impacting the environment include images of traffic-jammed highways, smoke-belching factories, and perhaps a few schools of fish floating belly-up in polluted water. Rarely do we see people working at their PCs or stacks of servers in data centers. Computers don't have exhaust pipes, but their environmental impact is no longer invisible. The cumulative life cycles of billions of machines, from manufacture to usage to disposal, are combining into an environmental footprint large enough to attract widespread attention.
Experiences of sparse direct symmetric solvers
Authors: Scott Jennifer A. , Hu Yifan
Published: September 2007

We recently carried out an extensive comparison of the performance of state-of-the-art sparse direct solvers for the numerical solution of symmetric linear systems of equations. Some of these solvers were written primarily as research codes while others have been developed for commercial use. Our experiences of using the different packages to solve a wide range of problems arising from real applications were mixed. In this paper, we highlight some of these experiences with the aim of providing advice to both software developers and users of sparse direct solvers. We discuss key features that a direct solver should offer and conclude that while performance is an essential factor to consider when choosing a code, there are other features that a user should also consider looking for that vary significantly between packages.
Efficient Gauss-related quadrature for two classes of logarithmic weight functions
Authors: Ball James S. , Beebe Nelson H. F.
Published: September 2007

Integrals with logarithmic singularities are often difficult to evaluate by numerical methods. In this work, a quadrature method is developed that allows the exact evaluation (up to machine accuracy) of integrals of polynomials with two general types of logarithmic weights.

The total work for the determination of
N
nodes and points of the quadrature method is O(
N
2
). Subsequently, integrals can be evaluated with O(
N
) operations and function evaluations, so the quadrature is efficient.

This quadrature method can then be used to generate the nonclassical orthogonal polynomials for weight functions containing logarithms and obtain Gauss and Gauss-related quadratures for these weights. Two algorithms for each of the two types of logarithmic weights that incorporate these methods are given in this paper.
Algorithm 867
Authors: Beebe Nelson H. F. , Ball James S.
Published: September 2007

A collection of subroutines and examples of their uses are described for the quadrature method developed in the companion article. These allow the exact evaluation (up to computer truncation and rounding errors) of integrals of polynomials with two general types of logarithmic weights, and also with the corresponding nonlogarithmic weights. The recurrence coefficients for the related nonclassical orthogonal polynomials with logarithmic weight functions can also be obtained. Tests of accuracy on various platforms are presented.

The routines are usable from Fortran, C, and C++ programs conforming to any of at least six international programming-language standards.
hpGEM---A software framework for discontinuous Galerkin finite element methods
Authors: Pesch Lars , Bell Alexander , Sollie Henk , Ambati Vijaya R. , Bokhove Onno , Van Der Vegt Jaap J. W.
Published: September 2007

hpGEM, a novel framework for the implementation of discontinuous Galerkin finite element methods (FEMs), is described. We present data structures and methods that are common for many (discontinuous) FEMs and show how we have implemented the components as an object-oriented framework. This framework facilitates and accelerates the implementation of finite element programs, the assessment of algorithms, and their application to real-world problems. The article documents the status of the framework, exemplifies aspects of its philosophy and design, and demonstrates the feasibility of the approach with several application examples.
deal.II—A general-purpose object-oriented finite element library
Authors: Bangerth W. , Hartmann R. , Kanschat G.
Published: September 2007

An overview of the software design and data abstraction decisions chosen for deal.II, a general purpose finite element library written in C++, is given. The library uses advanced object-oriented and data encapsulation techniques to break finite element implementations into smaller blocks that can be arranged to fit users requirements. Through this approach, deal.II supports a large number of different applications covering a wide range of scientific areas, programming methodologies, and application-specific algorithms, without imposing a rigid framework into which they have to fit. A judicious use of programming techniques allows us to avoid the computational costs frequently associated with abstract object-oriented class libraries.

The paper presents a detailed description of the abstractions chosen for defining geometric information of meshes and the handling of degrees of freedom associated with finite element spaces, as well as of linear algebra, input/output capabilities and of interfaces to other software, such as visualization tools. Finally, some results obtained with applications built atop deal.II are shown to demonstrate the powerful capabilities of this toolbox.
A parallel symmetric block-tridiagonal divide-and-conquer algorithm
Authors: Bai Yihua , Ward Robert C.
Published: September 2007

We present a parallel implementation of the block-tridiagonal divide-and-conquer algorithm that computes eigensolutions of symmetric block-tridiagonal matrices to reduced accuracy. In our implementation, we use mixed data/task parallelism to achieve data distribution and workload balance. Numerical tests show that our implementation is efficient, scalable and computes eigenpairs to prescribed accuracy. We compare the performance of our parallel eigensolver with that of the ScaLAPACK divide-and-conquer eigensolver on block-tridiagonal matrices.
Accurate numerical derivatives in MATLAB
Authors: Shampine L. F.
Published: September 2007

Complex step differentiation (CSD) is a technique for computing
very
accurate numerical derivatives in languages that support complex arithmetic. We describe here the development of a CSD package in MATLAB called PMAD. We have extended work done in other languages for scalars to the arrays that are fundamental to MATLAB. This extension raises questions that we have been able to resolve in a satisfactory way. Our goal has been to make it as easy as possible to compute approximate Jacobians in MATLAB that are all but exact. Although PMAD has a fast option for the expert that implements CSD as in previous work, the default is an object-oriented implementation that asks very little of the user.
Algorithm 869
Authors: Zwolak Jason W. , Boggs Paul T. , Watson Layne T.
Published: September 2007

ODRPACK (TOMS Algorithm 676) has provided a complete package for weighted orthogonal distance regression for many years. The code is complete with user selectable reporting facilities, numerical and analytic derivatives, derivative checking, and many more features. The foundation for the algorithm is a stable and efficient trust region Levenberg-Marquardt minimizer that exploits the structure of the orthogonal distance regression problem. ODRPACK95 was created to extend the functionality and usability of ODRPACK. ODRPACK95 adds bound constraints, uses the newer Fortran 95 language, and simplifies the interface to the user called subroutine.
Remark on Algorithm 644
Authors: Kodama Masao
Published: September 2007

This remark details correction for errors in the functions which compute the modified Bessel function of the second kind and the log of the gamma function. In both cases these errors cause a loss of precision for a small range of values of the ν argument. These routines are used in the calculation of a number of other functions within the package whose accuracy is thus similarly affected.
Modeling techniques
Authors: Dargie James
Published: September 2007

Computer graphic artists are constantly trying to emulate the real world. A main canvas that we paint reality on is the computer generated (CG) 3D model. CG models are used in a variety of ways for many disciplines. Although uses can run the gamut from medical visualization, accident recreation and entomology, main uses of this technology lie within the realm of movie visual effects and 3D gaming. The models themselves are not always accomplished the same way, and depend greatly upon which application it is being utilized in. The main difference between the two is that the CG movie model is simply built to be seen, while its video game cousin is built to interact with.
Modeling and improving data cache reliability
Authors: Kadayif Ismail , Kandemir Mahmut
Published: September 2007

Soft errors arising from energetic particle strikes pose a significant reliability concern for computing systems, especially for those running in noisy environments. Technology scaling and aggressive leakage control mechanisms make the problem caused by these transient errors even more severe. Therefore, it is very important to employ reliability enhancing mechanisms in processor/memory designs to protect them against soft errors. To do so, we first need to model soft errors, and then study cost/reliability tradeoffs among various reliability enhancing techniques based on the model so that system requirements could be met.

Since cache memories take the largest fraction of on-chip real estate today and their share is expected to continue to grow in future designs, they are more vulnerable to soft errors, as compared to many other components of a computing system. In this paper, we first focus on a soft error model for L1 data caches, and then explore different reliability enhancing mechanisms. More specifically, we define a metric called AVFC (Architectural Vulnerability Factor for Caches), which represents the probability with which a fault in the cache can be visible in the final output of the program. Based on this model, we then propose three architectural schemes for improving reliability in the existence of soft errors. Our first scheme prevents an error from propagating to the lower levels in the memory hierarchy by not forwarding the unmodified data words of a dirty cache block to the L2 cache when the dirty block is to be replaced. The second scheme proposed selectively invalidates cache blocks to reduce their vulnerable periods, decreasing their chances of catching any soft errors. Based on the AVFC metric, our experimental results show that these two schemes are very effective in alleviating soft errors in the L1 data cache. Specifically, by using our first scheme, it is possible to improve the AVFC metric by 32% without any performance loss. On the other hand, the second scheme enhances the AVFC metric between 60% and 97%, at the cost of a performance degradation which varies from 0% to 21.3%, depending on how aggressively the cache blocks are invalidated. To reduce the performance overhead caused by cache block invalidation, we also propose a third scheme which tries to bring a fresh copy of the invalidated block into the cache via prefetching. Our experimental results indicate that, this scheme can reduce the performance overheads to less than 1% for all applications in our experimental suite, at the cost of giving up a tolerable portion of the reliability enhancement the second scheme achieves.
QoS policies and architecture for cache/memory in CMP platforms
Authors: Iyer Ravi , Zhao Li , Guo Fei , Illikkal Ramesh , Makineni Srihari , Newell Don , Solihin Yan , Hsu Lisa , Reinhardt Steve
Published: September 2007

As we enter the era of CMP platforms with multiple threads/cores on the die, the diversity of the simultaneous workloads running on them is expected to increase. The rapid deployment of virtualization as a means to consolidate workloads on to a single platform is a prime example of this trend. In such scenarios, the quality of service (QoS) that each individual workload gets from the platform can widely vary depending on the behavior of the simultaneously running workloads. While the number of cores assigned to each workload can be controlled, there is no hardware or software support in today's platforms to control allocation of platform resources such as cache space and memory bandwidth to individual workloads. In this paper, we propose a QoS-enabled memory architecture for CMP platforms that addresses this problem. The QoS-enabled memory architecture enables more cache resources (i.e. space) and memory resources (i.e. bandwidth) for high priority applications based on guidance from the operating environment. The architecture also allows dynamic resource reassignment during run-time to further optimize the performance of the high priority application with minimal degradation to low priority. To achieve these goals, we will describe the hardware/software support required in the platform as well as the operating environment (O/S and virtual machine monitor). Our evaluation framework consists of detailed platform simulation models and a QoS-enabled version of Linux. Based on evaluation experiments, we show the effectiveness of a QoS-enabled architecture and summarize key findings/trade-offs.
Modeling the relative fitness of storage
Authors: Mesnier Michael P. , Wachs Matthew , Sambasivan Raja R. , Zheng Alice X. , Ganger Gregory R.
Published: September 2007

Relative fitness is a new black-box approach to modeling the performance of storage devices. In contrast with an absolute model that predicts the performance of a workload on a given storage device, a relative fitness model predicts performance
differences
between a pair of devices. There are two primary advantages to this approach. First, because are lative fitness model is constructed for a device pair, the application-device feedback of a closed workload can be captured (e.g., how the I/O arrival rate changes as the workload moves from device A to device B). Second, a relative fitness model allows performance and resource utilization to be used in place of workload characteristics. This is beneficial when workload characteristics are difficult to obtain or concisely express (e.g., rather than describe the spatio-temporal characteristics of a workload, one could use the observed cache behavior of device A to help predict the performance of B.

This paper describes the steps necessary to build a relative fitness model, with an approach that is general enough to be used with any black-box modeling technique. We compare relative fitness models and absolute models across a variety of workloads and storage devices. On average, relative fitness models predict bandwidth and throughput within 10-20% and can reduce prediction error by as much as a factor of two when compared to absolute models.
Facilitating focused internet measurements
Authors: Wen Zhihua , Triukose Sipat , Rabinovich Michael
Published: September 2007

This paper describes our implementation of and initial experiences with DipZoom (for "Deep Internet Performance Zoom"), a novel approach to provide focused, on-demand Internet measurements. Unlike existing approaches that face a difficult challenge of building a measurement platform with sufficiently diverse measurements and measuring hosts, DipZoom implements a matchmaking service instead, which uses P2P concepts to bring together experimenters in need of measurements with external measurement providers. DipZoom offers the following two main contributions. First,since it is just a facilitator for an open community of participants, it promises unprecedented availability of diverse measurements and measuring points. Second, it can be used as a veneer over existing measurement platforms, automating the planning and execution of complex measurements.