检索结果-内蒙古大学图书馆

On Scheduling Constraint Abstraction for Multi-Threaded Program Verification

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING 2020年第5期46卷 549-565页

作者： Yin, Liangze Dong, Wei Liu, Wanwei Wang, Ji Natl Univ Def Technol Sch Comp Lab Software Engn Complex Syst Changsha 410073 Hunan Peoples R China Natl Univ Def Technol Sch Comp State Key Lab High Performance Comp Lab Software Engn Complex Syst Changsha 410073 Hunan Peoples R China

Bounded model checking is among the most efficient techniques for the automated verification of concurrent programs. However, due to the nondeterministic thread interleavings, a large and complex formula is usually required to give an exact encoding of all possible behaviors, which significantly limits the scalability. Observing that the large formula is usually dominated by the exact encoding of the scheduling constraint, this paper proposes a novel scheduling constraint based abstraction refinement method for multi-threaded C program verification. Our method is both efficient in practice and complete in theory, which is challenging for existing techniques. To achieve this, we first proposed an effective and powerful technique which works well for nearly all benchmarks we evaluated. We have proposed the notion of Event Order Graph (EOG), and have devised two graph-based algorithms over EOG for counterexample validation and refinement generation, which can often obtain a small yet effective refinement constraint. Then, to ensure completeness, our method was enhanced with two constraint-based algorithms for counterexample validation and refinement generation. Experimental results on SV-COMP 2017 benchmarks and two real-world server systems indicate that our method is promising and significantly outperforms the state-of-the-art tools.

关键词： Instruction sets Electrooculography Encoding concurrent computing Programming Model checking Tools Multi-threaded program bounded model checking scheduling constraint event order graph

来源：评论

学校读者我要写书评

暂无评论

COMMUNICATING MODULES - A SOFTWARE-DESIGN MODEL FOR concurrent DISTRIBUTED SYSTEMS

引用

COMPUTER 1985年第1期18卷 67-77页

作者： WITT, BI IBM Federal Systems Division

First Page of the Article

关键词： Software design Logic design Packaging Application software Distributed processing concurrent computing Petri nets Process design Mathematical model

来源：评论

学校读者我要写书评

暂无评论

Back-end technology for high-performance knowledge-representation systems

引用

IEEE INTELLIGENT SYSTEMS & THEIR APPLICATIONS 1999年第3期14卷 63-69页

作者： Hendler, J Stoffel, K Univ Maryland Dept Comp Sci College Pk MD 20742 USA Univ Neuchatel Grp Informat CH-2000 Neuchatel Switzerland

Focuses on the significance of ontologies as an aspect of research in artificial intelligence systems. Integration of semantic models with large-scale data; Implementation of a system that support ontology-based appli... 详细信息

关键词： Ontologies Artificial intelligence Databases Cities and towns concurrent computing Memory management Intersymbol interference Internet Search engines Large scale integration

来源：评论

学校读者我要写书评

暂无评论

AN EXPERIMENTAL SINGLE-CHIP DATA FLOW CPU

引用

IEEE JOURNAL OF SOLID-STATE CIRCUITS 1992年第1期27卷 17-28页

作者： UVIEGHARA, GA HWU, WMW NAKAGOME, Y JEONG, DK LEE, DD HODGES, DA PATT, YN UNIV ILLINOIS DEPT ELECT & COMP ENGNURBANAIL 61801 HITACHI LTD CENT RES LABKOKUBUNJITOKYO 185JAPAN SEOUL NATL UNIV DEPT ELECTR ENGNSEOUL 151SOUTH KOREA XEROX CORP PALO ALTO RES CTRRES STAFFPALO ALTOCA 94304 UNIV CALIF BERKELEY DEPT ELECT ENGN & COMP SCIBERKELEYCA 94720 UNIV MICHIGAN DEPT ELECT ENGN & COMP SCIANN ARBORMI 48109 UNIV ILLINOIS IMPACT PROJECTURBANAIL 61801 UNIV CALIF BERKELEY COLL ENGNBERKELEYCA 94720

HPSm (high-performance substrate) is a single-chip data flow CPU [1], [2]. It enhances throughput by using three function units (two ALU's and one memory interface) to exploit parallelism, while executing RISC instructions in a data-driven manner to keep the function units busy. HPSm is data driven in the sense that instructions whose operands are not ready are not permitted to stall the machine by blocking subsequent ones. In other words, an instruction whose operands are available can be executed out of order, regardless of its position in the instruction stream, if previous instructions are not ready for execution. In addition, it achieves an additional speedup by employing branch prediction to exploit concurrency between blocks of code. By using three function units, it is capable of operating at a peak performance of 30 MIPS while running at only 10 MHz. HPSm reduces the disparity between the sustained and the peak performances by the out-of-order execution of instructions on the three function units. It employs four on-chip smart memories to control the data-driven execution on the three function units, and to support branch prediction and exception handling 131. Simulations indicate that HPSm achieves significant speedup over a single-chip RISC microarchitecture-the Berkeley SPUR-which is implemented with the same fabrication technology and clock cycle. The HPSm chip has been designed for a 1.6-mu-m double-metal scalable CMOS process. It contains 87 279 transistors, occupies an area of 13.83 mm x 13.04 mm, and is estimated to dissipate 2 W at 10 MHz.

关键词： Reduced instruction set computing Throughput concurrent computing Microarchitecture Fabrication CMOS technology Clocks CMOS process

来源：评论

学校读者我要写书评

暂无评论

KINEMATICALLY OPTIMAL HYPER-REDUNDANT MANIPULATOR CONFIGURATIONS

引用

IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION 1995年第6期11卷 794-806页

作者： CHIRIKJIAN, GS BURDICK, JW CALTECH DEPT MECH ENGNPASADENACA 91125

''Hyper-redundant'' robots have a very large or infinite degree of kinematic redundancy. This paper develops new methods for determining ''optimal'' hyper-redundant manipulator configurations based on a continuum formulation of kinematics. This formulation uses a backbone curve model to capture the robot's essential macroscopic geometric features. The calculus of variations is used to develop differential equations, whose solution is the optimal backbone curve shape. We show that this approach is computationally efficient on a single processor, and generates solutions in O(1) time for an N degree-of-freedom manipulator when implemented in parallel on O(N) processors. For this reason, it is better suited to hyper-redundant robots than other redundancy resolution methods. Furthermore, this approach is useful for many hyper-redundant mechanical morphologies which are not handled by known methods.

关键词： Manipulators Robots Kinematics Spine Solid modeling Calculus Differential equations Shape concurrent computing Morphology

来源：评论

学校读者我要写书评

暂无评论

USING THE DECOMPOSITION TREE FOR DIRECTED-NETWORK RELIABILITY COMPUTATION

引用

IEEE TRANSACTIONS ON RELIABILITY 1984年第5期33卷 390-395页

作者： HAGSTROM, JN University of Illinois Chicago USA

A related paper provides an algorithm to compute the reliability of an undirected network. The algorithm exploits the decomposition tree of the network derived from decomposing the network graph into its triconnected components. This paper extends the algorithm to apply to reliability problems involving directed networks. Details are presented which specialize the algorithm to apply to the problems of 2-terminal communication, transportation flow feasibility, and path-length feasibility.

关键词： Telecommunication network reliability Computer networks Tree graphs Algorithm design and analysis Transportation Reliability theory concurrent computing Probability distribution Bonding

来源：评论

学校读者我要写书评

暂无评论

A PORTABLE PARALLEL ALGORITHM FOR LOGIC SYNTHESIS USING TRANSDUCTION

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 1994年第5期13卷 566-580页

作者： DE, K RAMKUMAR, B BANERJEE, P UNIV IOWA DEPT ELECT & COMP ENGNIOWA CITYIA 52242 UNIV ILLINOIS COORDINATED SCI LABURBANAIL 61801

Combinational logic synthesis is a very important phase of VLSI system design. But the logic synthesis process requires large computing times if near optimal quality of the logic network is desired. Parallel processing is fast becoming an attractive solution to reduce the computational time. Recently, researchers have started to investigate parallel algorithms for problems in logic synthesis and verification. Much of the work in parallel algorithms for CAD reported to date, however, suffers from a major limitation. The parallel algorithms proposed for the CAD applications are designed with a specific underlying parallel architecture in mind. Moreover, incompatibilities in programming environments also make it difficult to port these programs across different parallel machines. As a result, a parallel algorithm needs to be developed afresh for every target parallel architecture. The ongoing project of ProperCAD offers an attractive solution to that problem. It allows the development and implementation of a parallel algorithm on the CHARM runtime system such that it can be executed in all the parallel machines without any change in the program. In this paper, we describe a portable parallel algorithm for logic synthesis based on the Transduction method, called ProperSYN. This algorithm uses an asynchronous message driven data-flow model of computation, with no explicit synchronizing barriers separating different phases of parallel computation as used in many previously developed parallel algorithms. Our algorithm is therefore more scalable to large numbers of processors. The algorithm has been implemented and it runs on a variety of parallel machines. We present results on several benchmark circuits for shared memory MIMD machine like Sequent Symmetry and Encore Multimax, distributed memory MIMD machine like the Intel/860 hypercube and distributed processing systems like networks of SUN workstations.

关键词： Parallel algorithms Network synthesis concurrent computing Parallel machines Design automation Parallel architectures Logic design Very large scale integration Computer networks Parallel processing

来源：评论

学校读者我要写书评

暂无评论

Vectorized transforms in scalar processors

引用

IEEE SIGNAL PROCESSING MAGAZINE 2002年第4期19卷 22-31页

作者： Trelewicz, JQ Mitchell, JL Brady, MT IBM Corp Almaden Res Ctr IBM Printing Syst Div Armonk NY 10504 USA

We disclose a generalized approach to creating efficient implementations of linear, orthogonal transforms, with specific examples discussed for the 8 x 8 DCT used in image compression. We connect this with a method for performing signed, parallel processing in scalar, off-the-shelf processors for integer transforms. Uniform data precision may be used, but is not required for the method. The coefficients resulting from the new algorithm converge more quickly than the approximation made to the coefficients. Furthermore, the new algorithm allows more control of the specific representation chosen for the coefficients, as is detailed below. The methods described were designed for addressing this need with two's-complement arithmetic. Data that can be processed in parallel, because of the algorithm structure, are packed in a "vector" format, described, into registers. Many signed arithmetic operations can be performed on these vectors, including addition, subtraction, multiplication by scalars, shifting, and others. When the parallel processing is completed, the vectors can be unpacked into scalar values for storage or subsequent processing. The importance of these methods lies in their handling of carries and borrows in the packed vector format. The generalized method is described. Notation is given at the beginning to establish consistency through the article. We discuss a generalized approach to integer transforms, using the DCT as a specific example. Then we detail the vector format, which allows vector computation in scalar processors of parallelizable algorithms. The IDCT is used as a numerical example in the discussion of the vector format. The results were developed for high-end printers (e.g., more than 100 pages per minute), where image compression and decompression must be performed in real time, either in FPGAs, or in embedded processors; however, the methods are applicable to a broad range of signal processing systems

关键词： Signal processing algorithms Discrete cosine transforms Image coding Parallel processing Arithmetic Approximation algorithms Image converters Design methodology concurrent computing Printers

来源：评论

学校读者我要写书评

暂无评论

Handling Concurrency in Behavior Trees

引用

IEEE TRANSACTIONS ON ROBOTICS 2022年第4期38卷 2557-2576页

作者： Colledanchise, Michele Natale, Lorenzo Ist Italiano Tecnol Ctr Robot & Intelligent Syst Humanoids Sensing & Percept Lab I-16163 Genoa Italy

This article addresses the concurrency issues affecting behavior trees (BTs), a popular tool to model the behaviors of autonomous agents in the video game and the robotics industry. BT designers can easily build complex behaviors composing simpler ones, which represents a key advantage of BTs. The parallel composition of BTs expresses a way to combine concurrent behaviors that has high potential, since composing pre-existing BTs in parallel results easier than composing in parallel classical control architectures, as finite state machines or teleo-reactive programs. However, BT designers rarely use such composition due to the underlying concurrency problems similar to the ones faced in concurrent programming. As a result, the parallel composition, despite its potential, finds application only in the composition of simple behaviors or where the designer can guarantee the absence of conflicts by design. In this article, we define two new BT nodes to tackle the concurrency problems in BTs and we show how to exploit them to create predictable behaviors. In addition, we introduce measures to assess execution performance and show how different design choices affect them. We validate our approach in both simulations and the real world. Simulated experiments provide statistically significant data, whereas real-world experiments show the applicability of our method on real robots. We provided an open-source implementation of the novel BT formulation and published all the source code to reproduce the numerical examples and experiments.

关键词： Robots Synchronization Task analysis Robot kinematics Programming Navigation concurrent computing Autonomous systems behavior trees behavior-based systems

来源：评论

学校读者我要写书评

暂无评论

Context and page analysis for improved Web search

引用

IEEE INTERNET computing 1998年第4期2卷 38-46页

作者： Lawrence, S Giles, CL NEC Res Inst Princeton NJ 08540 USA Univ Maryland Inst Adv Comp Studies College Pk MD 20742 USA

NEC Research Institute has developed a metasearch engine that improves that efficiency and precision of Web search by downloading and analyzing each document and then displaying the results that show the query terms in context. This technique is very effective, particularly when dealing with the Web's large, diverse, and poorly organized database. A description of the metasearch engine's features, implementation, and performance is presented.

关键词： Web search Search engines Metasearch National electric code Internet Computer displays Databases Web sites User interfaces concurrent computing

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：