11971991
Formal Reasoning about Concurrent Assembly Code with Reentrant Locks
This paper focuses on the problem of reasoning about concurrent assembly code with reentrant locks. Our verification technique is based on concurrent separation logic (CSL). In CSL, locks are treated as non-reentrant locks and each lock is associated with a resource invariant, the lock-protected resources are obtained and released through acquiring and releasing the lock respectively. In order to accommodate for reentrancy, we introduce some additional notions into our specification language to describe reentrant level for each acquiring and releasing lock operation. Keeping track of the reentrant level for each lock in the pre- and post- conditions enables the program logic to ensure that resources are not reacquired upon reentrancy, thus resources owned by a thread are prevented from reintroducing in the postcondition. Our framework is fully mechanized. Its soundness has been verified using the Coq proof assistant. We demonstrate the usage of our framework through giving a safety proof of a simple program.
15870104
Homomorphism Resolving of XPath Trees Based on Automata
As a query language for navigating XML trees and selecting a set of element nodes, XPath is ubiquitous in XML applications. One important issue of XPath queries is containment checking, which is known as a co-NP complete. The homomorphism relationship between two XPath trees, which is a PTIME problem, is a sufficient but not necessary condition for the containment relationship. We propose a new tree structure to depict XPath based on the level of the tree node and adopt a method of sharing the prefixes of multi-trees to construct incrementally the most effective automata, named XTHC (XPath Trees Homomorphism Checker). XTHC takes an XPath tree and produces the result of checking homomorphism relationship between an arbitrary tree in multi-trees and the input tree, thereinto the input tree is transformed into events which force the automata to run. Moreover, we consider and narrow the discrepancy between homomorphism relationship and containment relationship as possible as we can.
15507709
Data-Layout Optimization Using Reuse Distance Distribution
As the ever-increasing gap between the speed of processor and the speed of memory has become the cause of one of primary bottlenecks of computer systems, modern architecture systems use cache to solve this problem, whose utility heavily depends on program data locality. This paper introduces a platform independent data-layout optimization framework to improve program data locality. This framework uses a variable relation model based on variables’ reuse distance distribution to quantitate the relation of variables and accordingly assigns variables which are often accessed together in one group. At the same time this framework introduces a dynamic array regrouping method to group dynamic arrays assigned in a group. Experiments show that this data-layout optimization framework can effectively improve program data locality and program performance.
8620934
Certifying Concurrent Programs Using Transactional Memory
Transactional memory (TM) is a new promising concurrency-control mechanism that can avoid many of the pitfalls of the traditional lock-based techniques. TM systems handle data races between threads automatically so that programmers do not have to reason about the interaction of threads manually. TM provides a programming model that may make the development of multi-threaded programs easier. Much work has been done to explore the various implementation strategies of TM systems and to achieve better performance, but little has been done on how to formally reason about programs using TM and how to make sure that such reasoning is sound. In this paper, we focus on the semantics of transactional memory and present a proof-carrying code (PCC) system for reasoning about programs using TM. We formalize our reasoning with respect to the TM semantics, prove its soundness, and use examples to demonstrate its effectiveness.
21795877
An Eulerian Path Approach to Global Multiple Alignment for DNA Sequences
With the rapid increase in the dataset of genome sequences, the multiple sequence alignment problem is increasingly important and frequently involves the alignment of a large number of sequences. Many heuristic algorithms have been proposed to improve the speed of computation and the quality of alignment. We introduce a novel approach that is fundamentally different from all currently available methods. Our motivation comes from the Eulerian method for fragment assembly in DNA sequencing that transforms all DNA fragments into a de Bruijn graph and then reduces sequence assembly to a Eulerian path problem. The paper focuses on global multiple alignment of DNA sequences, where entire sequences are aligned into one configuration. Our main result is an algorithm with almost linear computational speed with respect to the total size (number of letters) of sequences to be aligned. Five hundred simulated sequences (averaging 500 bases per sequence and as low as 70% pairwise identity) have been aligned within three minutes on a personal computer, and the quality of alignment is satisfactory. As a result, accurate and simultaneous alignment of thousands of long sequences within a reasonable amount of time becomes possible. Data from an Arabidopsis sequencing project is used to demonstrate the performance.
17572677
Decision-Feedback Receiver for Quasi-Orthogonal Space-Time Coded OFDM Using Correlative Coding Over Fast Fading Channels
Orthogonal frequency division multiplexing (OFDM) is robust against frequency selective fading, but it is very vulnerable to time selective fading. In quasi-orthogonal space-time coded OFDM (ST-OFDM) systems, channel variations cause not only inter-carrier interference among different subcarriers in one OFDM block, but also inter-transmit-antenna interference (ITAI). When applied in fast fading channels, common ST-ODFM receivers usually suffer from an irreducible error floor. In this letter, we apply frequency-domain correlative coding combined with a modified decision-feedback detection scheme to effectively suppress the error floor of quasi-orthogonal ST-OFDM over fast fading channels. The effectiveness of the proposed scheme in mitigating the effects of channel time selectivity is demonstrated through comparison with existing schemes such as zero-forcing, two-stage zero-forcing, and sequential decision feedback estimation
6412815
Automated task distribution in multicore network processors using statistical analysis
Chip multiprocessor designs are the most common types of architectures seen in Network Processors. As the Network Processors are used to implement increasingly complicated applications, task distribution among the cores is becoming an important problem. In this paper, we propose a new task allocation scheme for such architectures. This scheme relies on the inherent modular nature of the networking applications and intelligently distributes modules among different execution cores. Additionally, we selectively replicate modules to parallelize execution of tasks having longer processing time. We have developed a technique that uses the probability distribution of the execution times of different modules in the networking applications. The proposed schemes result in resource utilization of up to 95%, 89%, and 84% on average for the processors with 2, 4, and 8 cores, respectively. The schemes are highly scalable and can improve the throughput by 6.72 times for 8 core processors, aggregated over four representative applications. The combination of selective replication of modules and variation-aware task allocation result in up to 12.5% (9.9% on average) performance improvement as compared to a scheme based on just mean processing time.
35901095
The Computational SLR: A Logic for Reasoning about Computational Indistinguishability
Computational indistinguishability is a notion in complexity-theoretic cryptography and is used to define many security criteria. However, in traditional cryptography, proving computational indistinguishability is usually informal and becomes error-prone when cryptographic constructions are complex. This paper presents a formal proof system based on an extension of Hofmann's SLR language, which can capture probabilistic polynomial-time computations through typing and is sufficient for expressing cryptographic constructions. We in particular define rules that justify directly the computational indistinguishability between programs and prove that these rules are sound with respect to the set-theoretic semantics, hence the standard definition of security. We also show that it is applicable in cryptography by verifying, in our proof system, Goldreich and Micali's construction of pseudorandom generator.
1600088
Automatic Acquisition of Context-Specific Lexical Paraphrases
Lexical paraphrasing aims at acquiring word-level paraphrases. It is critical for many Natural Language Processing (NLP) applications, such as Question Answering (QA), Information Extraction (IE), and Machine Translation (MT). Since the meaning and usage of a word can vary in distinct contexts, different paraphrases should be acquired according to the contexts. However, most of the existing researches focus on constructing paraphrase corpora, in which little contextual constraints for paraphrase application are imposed. This paper presents a method that automatically acquires context-specific lexical paraphrases. In this method, the obtained paraphrases of a word depend on the specific sentence the word occurs in. Two stages are included, i.e. candidate paraphrase extraction and paraphrase validation, both of which are mainly based on web mining. Evaluations are conducted on a news title corpus and the presented method is compared with a paraphrasing method that exploits a Chinese thesaurus of synonyms -- Tongyi Cilin (Extended) (CilinE for short). Results show that the f-measure of our method (0.4852) is significantly higher than that using CilinE (0.1127). In addition, over 85% of the correct paraphrases derived by our method cannot be found in CilinE, which suggests that our method is effective in acquiring out-of-thesaurus paraphrases.