DRAFT DRAFT DRAFT DRAFT DRAFT DRAFT DRAFT
- Iddo Lev
A common practice in Linguistics today is to analyze the meaning of natural language (NL) using logic. The meaning of a sentence is defined in terms of some truth conditions on a set-theoretical model structure. The translation from sentences to truth conditions is done via an intermediate precise logical language in a compositional way: each syntactic tree of a phrase in the NL is associated with an expression in the logical language (and thereby with a corresponding set-theoretic object in the model), and the meaning expression of a tree is determined by the meaning expressions of its subtrees. This logical...
Abstract Case Study: Testing of IP-based Mixed-Signal Fax/Modem System-on-Chip
- Sunho Chang; Lee-sup Kim; Seung-ho Hwang
Several test methods are applied for highly integrated mixed-signal Fax/Modem system-on-chip which consists of heterogeneous modules: MCU, DSP, PLA, memories, and CODEC. Top-level separate module testing is devised by test management unit which configures several IP-based module testing. External test programs are down-loaded on the embedded RAM and executed to evaluate the function of DSP in real-time which have 98.2 % fault coverage. Built-in self-test program is generated to test ROM and RAM. Individually accessible paths are designed for separate testing of each transmit and receive block in CODEC. Overall test logic has 1.2% additional chip area. 1.
GDP Festschrift ENTCS, to appear Abstract Local Reasoning about Data Update
- Cristiano Calcagno; Uri Zarfaty
We present local Hoare reasoning about data update, introducing Context Logic for analysing structured data. We apply our reasoning to tree update, heap update, and term rewriting. Our reasoning about heap update is exactly analogous to the local Hoare reasoning of Separation Logic. Our reasoning about tree update and term rewriting can only be done with Context Logic.
Efficient Goal Directed Bottom-up Evaluation of Logic Programs
Abstract This paper introduces a new strategy for the efficient goal directed bottomup evaluation of logic programs. Instead of combining a standard bottomup evaluation strategy with a Magic-set transformation, the evaluation strategy is specialized for the application to Magic-set programs which are characterized by clause bodies with a high degree of overlapping. The approach is similar to other techniques which avoid re-computation by maintaining and reusing partial solutions to clause bodies. However, the overhead is considerably reduced as these are maintained implicitly by the underlying Prolog implementation. The technique is presented as a simple meta-interpreter for goal directed bottom-up evaluation....
Hierarchical scheduling windows
- Edward Brekelbaum; Jeff Rupley Ii; Chris Wilkerson; Bryan Black
Large scheduling windows are an effective mechanism for increasing microprocessor performance through the extraction of instruction level parallelism. Current techniques do not scale effectively for very large windows, leading to slow wakeup and select logic as well as large complicated bypass networks. This paper introduces a new instruction scheduler implementation, referred to as Hierarchical Scheduling Windows or HSW, which exploits latency tolerant instructions in order to reduce implementation complexity. HSW yields a very large instruction window that tolerates wakeup, select, and bypass latency, while extracting significant far-flung ILP. Results: It is shown that HSW loses <0.5 % performance per additional...
Functional Verification of 622-Mbps–6.375-Gbps Transceiver IP in an FPGA
- Ning Xue; Altera Corporation; Arch Zaliznyak
The process of verifying a configurable IP is more complex and time-consuming than the IP design. This paper discusses a “divide-and-conquer ” functional verification methodology for a highly configurable multi-gigabit transceiver IP used in a FPGA. Verification methods, reusability, hardware emulation and mixed-signal validation are covered to show how the IP is efficiently verified for tape-out. The advantages of the presented method include comprehensive test coverage, test bench re-usability in chip simulations, hardware emulation and lab bring up, and improved verification efficiency. Author Biography Ning Xue is currently a senior member of the technical staff at Altera Corporation specializing in...
The Threading-4pproxh to The Immerse Protein Folding Problem
- Jadwiga Bierkowska Bob Rogers; Richard Lathropt
The logic behind the threading approach to the prediction of an amino acid sequence’s expected three-dimensional fold is almost seductively simple, if not obvious. Given the extreme difficulty of any direct. de notlo, quantum!evel approach
Incentive Issues in R&D Consortia: Insights from Applied Game Theory 1
- Eran Binenbaum
Abstract: This paper sketches how insights from applied game theory can be applied to R&D consortia, using a case study on an international plant breeding consortium. The insights jointly comprise a new “logic of collective action in R&D, ” which is inspired by Olson’s Logic of Collective Action but goes beyond it. We analyze R&D consortia as institutions that respond to a variety of incentive problems which are obstacles to realizing the benefits of cooperation that arise due to the public-goods nature of outputs, complementarities of inputs, and economies of scale and scope. Additionally, we sketch a “big-picture” consortium game...
- Il-woong Kim; Gunbae Kim
Abstract – Systems-on-Chip(SoC)s are now moving from logic dominant to memory dominant chips in order to satisfy high functionality and short development cycle. This means that the yield of memory part is the most important factor for the entire chip yield. In this paper, two word-oriented memory test algorithms are proposed newly. The one is an efficient writing NPSF test algorithm and the other is an efficient disturb test algorithm. Finally, we describe an BIST architecture for word-oriented embedded memory that detects basic FFMs, DFs, NPSFs,
Local reasoning for storable locks and threads
- Alexey Gotsman; Josh Berdine; Byron Cook; Noam Rinetzky; Mooly Sagiv
Abstract. We present a resource oriented program logic that is able to reason about concurrent heap-manipulating programs with unbounded numbers of dynamically-allocated locks and threads. The logic is inspired by concurrent separation logic, but handles these more realistic concurrency primitives. We demonstrate that the proposed logic allows local reasoning about programs for which there exists a notion of dynamic ownership of heap parts by locks and threads. 1
VITAL Visualization and Implementation of Temporal Action Logic
Since a large amount of code is shared between VITAL and TALplanner, including the parser, many of the language constructions are identical or very similar for both tools. Instead of writing two completely separate manuals and duplicating a large amount of text, minor differences between the two languages will be pointed out in this manual, and the TALplanner language manual often refers back to this document. The input language contains a number of extensions to the plain L(ND) language. Many of these extensions are experimental, and may either disappear in the future or be provided with a formal translation into...
Relational parametricity and separation logic
- Lars Birkedal; Hongseok Yang
Abstract. Separation logic is a recent extension of Hoare logic for reasoning about programs with references to shared mutable data structures. In this paper, we provide a new interpretation of the logic for a programming language with higher types. Our interpretation is based on Reynolds’s relational parametricity, and it provides a formal connection between separation logic and data abstraction. 1.
Adaptive Power Control Module in Cellular Radio System
- Jianhua Gan
Adaptive power control scheme based on the optimization of transmitter power and receiver filter coefficients is shown. The scheme is mapped to control logic, digital filter and adaptive amplifier. Accurate power control can reduce the interference in both Global System Mobile (GSM) and CDMA system. When the mobile is close to the base station, it can use lower power since the signal loss is smaller. For GSM, interference to other cells using the same frequency is reduced when the power control is accurate. For CDMA, accurate power control is more important because all CDMA signals interfere with each other. Lack...
Using first-order theorem provers in the Jahob data structure verification system
- Charles Bouillaguet; Viktor Kuncak; Thomas Wies; Karen Zee; Martin Rinard
Abstract. This paper presents our integration of efficient resolution-based theorem provers into the Jahob data structure verification system. Our experimental results show that this approach enables Jahob to automatically verify the correctness of a range of complex dynamically instantiable data structures, including data structures such as hash tables and search trees, without the need for interactive theorem proving or techniques tailored to individual data structures. Our primary technical results include: (1) a translation from higher-order logic to first-order logic that enables the application of resolution-based theorem provers and (2) a proof that eliminating type (sort) information in formulas is both...
A logic for encapsulation in object oriented languages
- Michele Bugliesi; Hasan M. Jamil
The language F-logic proposed by Kifer et al.  is a very nice declarative formalism for OODBs and is regarded as one of the best developed proposals so far. The work on F-Logic has provided foundations for a whole suite of research in the field of deductive object-oriented databases. Among others, a fundamental merit of this proposal is that it has a very solid logical foundation with "a sound and complete proof theory " .
Overview of Logic and Computation: Notes
- John Slaney; If Γ A
We study formal logic as a mathematical tool for reasoning and as a medium for knowledge representation. The central notion is that of a consequence relation defined over a formal language of some kind. This is intended to capture the intuitive concept of valid inference or entailment, at least in that it provides a catalogue of valid argument forms. 1.1 Consequence relations At the most abstract level, we do not say what is in the language, except that it is a set of objects which we may call sentences or, more neutrally, formulae. A set of formulae (assumptions or premises)...
Pattern-Directed Circuit Virtual Partitioning for Test Power Reduction
- Qiang Xu
For a large circuit under test (CUT), it is likely that some test patterns result in excessive power dissipations that exceed the CUT’s power rating. Designers may resort to lowpower automatic test pattern generation (ATPG) tools to solve this problem, which, however, usually leads to larger test data volume and requires extra computational effort, even if such tools are available. Another method is to partition the circuit into multiple subcircuits and test them separately. Unfortunately, this usually involves rerunning the time-consuming ATPG for each partitioned subcircuit and solving the problem of how to achieve an acceptable fault coverage for the...
SafeResynth: A New Technique for Physical Synthesis
- Kai-hui Chang; Igor L. Markov; Valeria Bertacco
Physical synthesis is a relatively young field in Electronic Design Automation. Many published optimizations for physical synthesis end up hurting the quality of the final design, often because they neglect important physical aspects of the layout, such as long wires or routing congestion. Our work defines and explores the concept of physical safeness and evaluates empirically its impact on route length, via count and timing. In addition, we propose a new physically safe and logically sound optimization, called SafeResynth, which provides immediately-measurable improvements without altering the design’s functionality. SafeResynth can enhance circuit timing without detrimental effects on route length and...
A tagged LCF-style proof architecture
- Konrad Slind
Abstract. We describe the notion of tagged inference as it arises in LCF-style theorem proving systems. Adding tags considerably widens the applicability of such systems, while costing little. By way of introduction, we give a simple tagged implementation of a propositional logic. We also discuss how tagged inference is currently used in an industrial strength proof system. Some knowledge of ML is assumed. 1 Introduction The LCF methodology for implementing theorem proving systems is well-known and has resulted in some relatively widely used theorem proving systems [2, 8, 11, 5]. LCF  was an influential system on many counts, introducing...
Optimizing polynomial expressions by algebraic factorization and common subexpression elimination
- Anup Hosangadi; Student Member; Farzan Fallah; Ryan Kastner
Abstract—Polynomial expressions are frequently encountered in many application domains, particularly in signal processing and computer graphics. Conventional compiler techniques for redundancy elimination such as common subexpression elimination (CSE) are not suited for manipulating polynomial expressions, and designers often resort to hand optimizing these expressions. This paper leverages the algebraic techniques originally developed for multilevel logic synthesis to optimize polynomial expressions by factoring and eliminating common subexpressions. The proposed algorithm was tested on a set of benchmark polynomial expressions where savings of 26.7 % in latency and 26.4 % in energy consumption were observed for computing these expressions on the StrongARM...