OpenRaiser/Intern-Atlas huggingface dataset:
Remarks on Jurdzinski and Lorys' proof that palindromes are not a Church-Rosser language
Venue: arXiv cs.LO 2007
Year: 2007

In 2002 Jurdzinski and Lorys settled a long-standing conjecture that palindromes are not a Church-Rosser language. Their proof required a sophisticated theory about computation graphs of 2-stack automata. We present their proof in terms of 1-tape Turing machines.We also provide an alternative proof of Buntrock and Otto's result that the set of non-square bitstrings, which is context-free, is not Church-Rosser.
Space-Efficient Bounded Model Checking
Venue: arXiv cs.LO 2007
Year: 2007

Current algorithms for bounded model checking use SAT methods for checking satisfiability of Boolean formulae. These methods suffer from the potential memory explosion problem. Methods based on the validity of Quantified Boolean Formulae (QBF) allow an exponentially more succinct representation of formulae to be checked, because no "unrolling" of the transition relation is required. These methods have not been widely used, because of the lack of an efficient decision procedure for QBF. We evaluate the usage of QBF in bounded model checking (BMC), using general-purpose SAT and QBF solvers. We develop a special-purpose decision procedure for QBF used in BMC, and compare our technique with the methods using general-purpose SAT and QBF solvers on real-life industrial benchmarks.
Nano-Sim: A Step Wise Equivalent Conductance based Statistical Simulator for Nanotechnology Circuit Design
Venue: arXiv cs.PF 2007
Year: 2007

New nanotechnology based devices are replacing CMOS devices to overcome CMOS technology's scaling limitations. However, many such devices exhibit non-monotonic I-V characteristics and uncertain properties which lead to the negative differential resistance (NDR) problem and the chaotic performance. This paper proposes a new circuit simulation approach that can effectively simulate nanotechnology devices with uncertain input sources and negative differential resistance (NDR) problem. The experimental results show a 20-30 times speedup comparing with existing simulators.
At-Speed Logic BIST for IP Cores
Venue: arXiv cs.AR 2007
Year: 2007

This paper describes a flexible logic BIST scheme that features high fault coverage achieved by fault-simulation guided test point insertion, real at-speed test capability for multi-clock designs without clock frequency manipulation, and easy physical implementation due to the use of a low-speed SE signal. Application results of this scheme to two widely used IP cores are also reported.
Synchronization Processor Synthesis for Latency Insensitive Systems
Venue: arXiv cs.AR 2007
Year: 2007

In this paper we present our contribution in terms of synchronization processor for a SoC design methodology based on the theory of the latency insensitive systems (LIS) of Carloni et al. Our contribution consists in IP encapsulation into a new wrapper model which speed and area are optimized and synthetizability guarantied. The main benefit of our approach is to preserve the local IP performances when encapsulating them and reduce SoC silicon area.
RIP: An Efficient Hybrid Repeater Insertion Scheme for Low Power
Venue: arXiv cs.OH 2007
Year: 2007

This paper presents a novel repeater insertion algorithm for interconnect power minimization. The novelty of our approach is in the judicious integration of an analytical solver and a dynamic programming based method. Specifically, the analytical solver chooses a concise repeater library and a small set of repeater location candidates such that the dynamic programming algorithm can be performed fast with little degradation of the solution quality. In comparison with previously reported repeater insertion schemes, within comparable runtimes, our approach achieves up to 37% higher power savings. Moreover, for the same design quality, our scheme attains a speedup of two orders of magnitude.
Cantilever-Based Biosensors in CMOS Technology
Venue: arXiv cs.AR 2007
Year: 2007

Single-chip CMOS-based biosensors that feature microcantilevers as transducer elements are presented. The cantilevers are functionalized for the capturing of specific analytes, e.g., proteins or DNA. The binding of the analyte changes the mechanical properties of the cantilevers such as surface stress and resonant frequency, which can be detected by an integrated Wheatstone bridge. The monolithic integrated readout allows for a high signal-to-noise ratio, lowers the sensitivity to external interference and enables autonomous device operation.
A Prediction Packetizing Scheme for Reducing Channel Traffic in Transaction-Level Hardware/Software Co-Emulation
Venue: arXiv cs.PF 2007
Year: 2007

This paper presents a scheme for efficient channel usage between simulator and accelerator where the accelerator models some RTL sub-blocks in the accelerator-based hardware/software co-simulation while the simulator runs transaction-level model of the remaining part of the whole chip being verified. With conventional simulation accelerator, evaluations of simulator and accelerator alternate at every valid simulation time, which results in poor simulation performance due to startup overhead of simulator-accelerator channel access. The startup overhead can be reduced by merging multiple transactions on the channel into a single burst traffic. We propose a predictive packetizing scheme for reducing channel traffic by merging as many transactions into a burst traffic as possible based on 'prediction and rollback.' Under ideal condition with 100% prediction accuracy, the proposed method shows a performance gain of 1500% compared to the conventional one.
IEEE 1149.4 Compatible ABMs for Basic RF Measurements
Venue: arXiv cs.AR 2007
Year: 2007

An analogue testing standard IEEE 1149.4 is mainly targeted for low-frequency testing. The problem studied in this paper is extending the standard also for radio frequency testing. IEEE 1149.4 compatible measurement structures (ABMs) developed in this study extract the information one is measuring from the radio frequency signal and represent the result as a DC voltage level. The ABMs presented in this paper are targeted for power and frequency measurements operating in frequencies from 1 GHz to 2 GHz. The power measurement error caused by temperature, supply voltage and process variations is roughly 2 dB and the frequency measurement error is 0.1 GHz, respectively.
Top-Down Design of a Low-Power Multi-Channel 2.5-Gbit/s/Channel Gated Oscillator Clock-Recovery Circuit
Venue: arXiv cs.AR 2007
Year: 2007

We present a complete top-down design of a low-power multi-channel clock recovery circuit based on gated current-controlled oscillators. The flow includes several tools and methods used to specify block constraints, to design and verify the topology down to the transistor level, as well as to achieve a power consumption as low as 5mW/Gbit/s. Statistical simulation is used to estimate the achievable bit error rate in presence of phase and frequency errors and to prove the feasibility of the concept. VHDL modeling provides extensive verification of the topology. Thermal noise modeling based on well-known concepts delivers design parameters for the device sizing and biasing. We present two practical examples of possible design improvements analyzed and implemented with this methodology.
Leakage-Aware Interconnect for On-Chip Network
Venue: arXiv cs.AR 2007
Year: 2007

On-chip networks have been proposed as the interconnect fabric for future systems-on-chip and multi-processors on chip. Power is one of the main constraints of these systems and interconnect consumes a significant portion of the power budget. In this paper, we propose four leakage-aware interconnect schemes. Our schemes achieve 10.13%~63.57% active leakage savings and 12.35%~95.96% standby leakage savings across schemes while the delay penalty ranges from 0% to 4.69%.
Worst-Case and Average-Case Analysis of n-Detection Test Sets
Venue: arXiv cs.AR 2007
Year: 2007

Test sets that detect each target fault n times (n-detection test sets) are typically generated for restricted values of n due to the increase in test set size with n. We perform both a worst-case analysis and an average-case analysis to check the effect of restricting n on the unmodeled fault coverage of an (arbitrary) n-detection test set. Our analysis is independent of any particular test set or test generation approach. It is based on a specific set of target faults and a specific set of untargeted faults. It shows that, depending on the circuit, very large values of n may be needed to guarantee the detection of all the untargeted faults. We discuss the implications of these results.
A New Approach to Component Testing
Venue: arXiv cs.OH 2007
Year: 2007

Carefully tested electric/electronic components are a requirement for effective hardware-in-the-loop tests and vehicle tests in automotive industry. A new method for definition and execution of component tests is described. The most important advantage of this method is independance from the test stand. It therefore offers the oppportunity to build up knowledge over a long period of time and the ability to share this knowledge with different partners.
Verifying Safety-Critical Timing and Memory-Usage Properties of Embedded Software by Abstract Interpretation
Venue: arXiv cs.LO 2007
Year: 2007

Static program analysis by abstract interpretation is an efficient method to determine properties of embedded software. One example is value analysis, which determines the values stored in the processor registers. Its results are used as input to more advanced analyses, which ultimately yield information about the stack usage and the timing behavior of embedded software.
A Fast Concurrent Power-Thermal Model for Sub-100nm Digital ICs
Venue: arXiv cs.AR 2007
Year: 2007

As technology scales down, the static power is expected to become a significant fraction of the total power. The exponential dependence of static power with the operating temperature makes the thermal profile estimation of high-performance ICs a key issue to compute the total power dissipated in next-generations. In this paper we present accurate and compact analytical models to estimate the static power dissipation and the temperature of operation of CMOS gates. The models are the fundamentals of a performance estimation tool in which numerical procedures are avoided for any computation to set a faster estimation and optimization. The models developed are compared to measurements and SPICE simulations for a 0.12mm technology showing excellent results.
Access Pattern-Based Code Compression for Memory-Constrained Embedded Systems
Venue: arXiv cs.OH 2007
Year: 2007

As compared to a large spectrum of performance optimizations, relatively little effort has been dedicated to optimize other aspects of embedded applications such as memory space requirements, power, real-time predictability, and reliability. In particular, many modern embedded systems operate under tight memory space constraints. One way of satisfying these constraints is to compress executable code and data as much as possible. While research on code compression have studied efficient hardware and software based code strategies, many of these techniques do not take application behavior into account, that is, the same compression/decompression strategy is used irrespective of the application being optimized. This paper presents a code compression strategy based on control flow graph (CFG) representation of the embedded program. The idea is to start with a memory image wherein all basic blocks are compressed, and decompress only the blocks that are predicted to be needed in the near future. When the current access to a basic block is over, our approach also decides the point at which the block could be compressed. We propose several compression and decompression strategies that try to reduce memory requirements without excessively increasing the original instruction cycle counts.
A Constraint Network Based Approach to Memory Layout Optimization
Venue: arXiv cs.PL 2007
Year: 2007

While loop restructuring based code optimization for array intensive applications has been successful in the past, it has several problems such as the requirement of checking dependences (legality issues) and transformation of all of the array references within the loop body indiscriminately (while some of the references can benefit from the transformation, others may not). As a result, data transformations, i.e., transformations that modify memory layout of array data instead of loop structure have been proposed. One of the problems associated with data transformations is the difficulty of selecting a memory layout for an array that is acceptable to the entire program (not just to a single loop). In this paper, we formulate the problem of determining the memory layouts of arrays as a constraint network, and explore several methods of solution in a systematic way. Our experiments provide strong support in favor of employing constraint processing, and point out future research directions.
Queue Management in Network Processors
Venue: arXiv cs.AR 2007
Year: 2007

One of the main bottlenecks when designing a network processing system is very often its memory subsystem. This is mainly due to the state-of-the-art network links operating at very high speeds and to the fact that in order to support advanced Quality of Service (QoS), a large number of independent queues is desirable. In this paper we analyze the performance bottlenecks of various data memory managers integrated in typical Network Processing Units (NPUs). We expose the performance limitations of software implementations utilizing the RISC processing cores typically found in most NPU architectures and we identify the requirements for hardware assisted memory management in order to achieve wire-speed operation at gigabit per second rates. Furthermore, we describe the architecture and performance of a hardware memory manager that fulfills those requirements. This memory manager, although it is implemented in a reconfigurable technology, it can provide up to 6.2Gbps of aggregate throughput, while handling 32K independent queues.
Direct Conversion Pulsed UWB Transceiver Architecture
Venue: arXiv cs.NI 2007
Year: 2007

Ultra-wideband (UWB) communication is an emerging wireless technology that promises high data rates over short distances and precise locationing. The large available bandwidth and the constraint of a maximum power spectral density drives a unique set of system challenges. This paper addresses these challenges using two UWB transceivers and a discrete prototype platform.
Performance Considerations for an Embedded Implementation of OMA DRM 2
Venue: arXiv cs.CR 2007
Year: 2007

As digital content services gain importance in the mobile world, Digital Rights Management (DRM) applications will become a key component of mobile terminals. This paper examines the effect dedicated hardware macros for specific cryptographic functions have on the performance of a mobile terminal that supports version 2 of the open standard for Digital Rights Management defined by the Open Mobile Alliance (OMA). Following a general description of the standard, the paper contains a detailed analysis of the cryptographic operations that have to be carried out before protected content can be accessed. The combination of this analysis with data on execution times for specific algorithms realized in hardware and software has made it possible to build a model which has allowed us to assert that hardware acceleration for specific cryptographic algorithms can significantly reduce the impact DRM has on a mobile terminal's processing performance and battery life.
A High Quality/Low Computational Cost Technique for Block Matching Motion Estimation
Venue: arXiv cs.MM 2007
Year: 2007

Motion estimation is the most critical process in video coding systems. First of all, it has a definitive impact on the rate-distortion performance given by the video encoder. Secondly, it is the most computationally intensive process within the encoding loop. For these reasons, the design of high-performance low-cost motion estimators is a crucial task in the video compression field. An adaptive cost block matching (ACBM) motion estimation technique is presented in this paper, featuring an excellent tradeoff between the quality of the reconstructed video sequences and the computational effort. Simulation results demonstrate that the ACBM algorithm achieves a slight better rate-distortion performance than the one given by the well-known full search algorithm block matching algorithm with reductions of up to 95% in the computational load.
FPGA based Agile Algorithm-On-Demand Co-Processor
Venue: arXiv cs.AR 2007
Year: 2007

With growing computational needs of many real-world applications, frequently changing specifications of standards, and the high design and NRE costs of ASICs, an algorithm-agile FPGA based co-processor has become a viable alternative. In this article, we report about the general design of an algorith-agile co-processor and the proof-of-concept implementation.
The Integration of On-Line Monitoring and Reconfiguration Functions using EDAA - European design and Automation Association1149.4 Into a Safety Critical Automotive Electronic Control Unit
Venue: arXiv cs.AR 2007
Year: 2007

This paper presents an innovative application of EDAA - European design and Automation Association 1149.4 and the Integrated Diagnostic Reconfiguration (IDR) as tools for the implementation of an embedded test solution for an Automotive Electronic Control Unit implemented as a fully integrated mixed signal system. The paper described how the test architecture can be used for fault avoidance with results from a hardware prototype presented. The paper concludes that fault avoidance can be integrated into mixed signal electronic systems to handle key failure modes.
A CMOS-Based Tactile Sensor for Continuous Blood Pressure Monitoring
Venue: arXiv cs.OH 2007
Year: 2007

A monolithic integrated tactile sensor array is presented, which is used to perform non-invasive blood pressure monitoring of a patient. The advantage of this device compared to a hand cuff based approach is the capability of recording continuous blood pressure data. The capacitive, membrane-based sensor device is fabricated in an industrial CMOS-technology combined with post-CMOS micromachining. The capacitance change is detected by a S?-modulator. The modulator is operated at a sampling rate of 128kS/s and achieves a resolution of 12bit with an external decimation filter and an OSR of 128.
Evaluation of SystemC Modelling of Reconfigurable Embedded Systems
Venue: arXiv cs.AR 2007
Year: 2007

This paper evaluates the use of pin and cycle accurate SystemC models for embedded system design exploration and early software development. The target system is MicroBlaze VanillaNet Platform running MicroBlaze uClinux operating system. The paper compares Register Transfer Level (RTL) Hardware Description Language (HDL) simulation speed to the simulation speed of several different SystemC models. It is shown that simulation speed of pin and cycle accurate models can go up to 150 kHz, compared to 100 Hz range of HDL simulation. Furthermore, utilising techniques that temporarily compromise cycle accuracy, effective simulation speed of up to 500 kHz can be obtained.
Social Media as Windows on the Social Life of the Mind
Venue: arXiv cs.CY 2007
Year: 2007

This is a programmatic paper, marking out two directions in which the study of social media can contribute to broader problems of social science: understanding cultural evolution and understanding collective cognition. Under the first heading, I discuss some difficulties with the usual, adaptationist explanations of cultural phenomena, alternative explanations involving network diffusion effects, and some ways these could be tested using social-media data. Under the second I describe some of the ways in which social media could be used to study how the social organization of an epistemic community supports its collective cognitive performance.
Connection Between System Parameters and Localization Probability in Network of Randomly Distributed Nodes
Venue: arXiv cs.NI 2007
Year: 2007

This article deals with localization probability in a network of randomly distributed communication nodes contained in a bounded domain. A fraction of the nodes denoted as L-nodes are assumed to have localization information while the rest of the nodes denoted as NL nodes do not. The basic model assumes each node has a certain radio coverage within which it can make relative distance measurements. We model both the case radio coverage is fixed and the case radio coverage is determined by signal strength measurements in a Log-Normal Shadowing environment. We apply the probabilistic method to determine the probability of NL-node localization as a function of the coverage area to domain area ratio and the density of L-nodes. We establish analytical expressions for this probability and the transition thresholds with respect to key parameters whereby marked change in the probability behavior is observed. The theoretical results presented in the article are supported by simulations.
Escalating The War On SPAM Through Practical POW Exchange
Venue: arXiv cs.NI 2007
Year: 2007

Proof-of-work (POW) schemes have been proposed in the past. One prominent system is HASHCASH (Back, 2002) which uses cryptographic puzzles . However, work by Laurie and Clayton (2004) has shown that for a uniform proof-of-work scheme on email to have an impact on SPAM, it would also be onerous enough to impact on senders of "legitimate" email. I suggest that a non-uniform proof-of-work scheme on email may be a solution to this problem, and describe a framework that has the potential to limit SPAM, without unduly penalising legitimate senders, and is constructed using only current SPAM filter technology, and a small change to the SMTP (Simple Mail Transfer Protocol). Specifically, I argue that it is possible to make sending SPAM 1,000 times more expensive than sending "legitimate" email (so called HAM). Also, unlike the system proposed by Debin Liu and Jean Camp (2006), it does not require the complications of maintaining a reputation system.
Discriminated Belief Propagation
Venue: arXiv cs.IT 2007
Year: 2007

Near optimal decoding of good error control codes is generally a difficult task. However, for a certain type of (sufficiently) good codes an efficient decoding algorithm with near optimal performance exists. These codes are defined via a combination of constituent codes with low complexity trellis representations. Their decoding algorithm is an instance of (loopy) belief propagation and is based on an iterative transfer of constituent beliefs. The beliefs are thereby given by the symbol probabilities computed in the constituent trellises. Even though weak constituent codes are employed close to optimal performance is obtained, i.e., the encoder/decoder pair (almost) achieves the information theoretic capacity. However, (loopy) belief propagation only performs well for a rather specific set of codes, which limits its applicability. In this paper a generalisation of iterative decoding is presented. It is proposed to transfer more values than just the constituent beliefs. This is achieved by the transfer of beliefs obtained by independently investigating parts of the code space. This leads to the concept of discriminators, which are used to improve the decoder resolution within certain areas and defines discriminated symbol beliefs. It is shown that these beliefs approximate the overall symbol probabilities. This leads to an iteration rule that (below channel capacity) typically only admits the solution of the overall decoding problem. Via a Gauss approximation a low complexity version of this algorithm is derived. Moreover, the approach may then be applied to a wide range of channel maps without significant complexity increase.