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

25th Annual IEEE Symposium on Logic in Computer Science (LICS)

作者： Broadbent, Christopher H. Carayol, Arnaud Ong, C-H. Luke Serre, Olivier Univ Oxford Comp Lab Oxford OX1 2JD England Univ Paris Est LIGM CNRS Paris France Univ Paris 07 LIAFA CNRS F-75221 Paris 05 France

ISBN: (纸本)9780769541143

Let R be a class of generators of node-labelled infinite trees, and L be a logical language for describing correctness properties of these trees. Given R is an element of R and phi is an element of L, we say that R-phi is a phi-reflection of R just if (i) R and R. generate the same underlying tree, and (ii) suppose a node u of the tree [[R]] generated by R has label f, then the label of the node u of [[R.]] is (f) under bar if u in [[R]] satisfies phi;it is f otherwise. Thus if [[R]] is the computation tree of a program R, we may regard R-phi as a transform of R that can internally observe its behaviour against a specification phi. We say that R is (constructively) reflective w.r.t. L just if there is an algorithm that transforms a given pair (R, phi) to R-phi. In this paper, we prove that higher-order recursion schemes are reflective w.r.t. both modal mu-calculus and monadic second order (MSO) logic. To obtain this result, we give the first characterisation of the winning regions of parity games over the transition graphs of collapsible pushdown automata (CPDA): they are regular sets defined by a new class of automata. (Order-n recursion schemes are equi-expressive with order-n CPDA for generating trees.) As a corollary, we show that these schemes are closed under the operation of MSO-interpretation followed by tree unfolding a la Caucal.

关键词： Î¼-calculus Collapsible Pushdown Automata Monadic Second Order Logic and Mu-Calculus Global model checking Parity Games Recursion Schemes automata collapsible pushdown automata higher order recursion scheme logical language monadic second order logic program control structures pushdown automata transform transforms tree trees (mathematics)

来源：评论

学校读者我要写书评

暂无评论

Efficient discovery of loop nests in execution traces

Efficient discovery of loop nests in execution traces

引用

International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems

作者： Xu, Qiang Subhlok, Jaspal Hammen, Nathaniel CGGVeritas Inc. United States Department of Computer Science University of Houston United States

ISBN: (纸本)9780769541976

Execution and communication traces are central to performance modeling and analysis. Since the traces can be very long, meaningful compression and extraction of representative behavior is important. Commonly used compression procedures identify repeating patterns in sections of the input string and replace each instance with a representative symbol. This can prevent the identification of long repeating sequences corresponding to outer loops in a trace. This paper introduces and analyzes a framework for identifying the maximal loop nest from a trace. The discovery of loop nests makes construction of compressed representative traces straightforward. The paper also introduces a greedy algorithm for fast "near optimal" loop nest discovery with well defined bounds. Results of compressing MPI communication traces of NAS parallel benchmarks show that both algorithms identified the basic loop structures correctly. The greedy algorithm was also very efficient with an average processing time of 16.5 seconds for an average trace length of 71695 MPI events. © 2010 IEEE.

关键词： MPI communication traces NAS parallel benchmarks Trace compression application program interfaces execution traces greedy algorithm greedy algorithms loop discovery loop structures message passing near optimal loop nest discovery performance modeling program control structures repeating patterns repeating sequences

来源：评论

学校读者我要写书评

暂无评论

Non-Termination Analysis of Linear Loop programs with Conditionals

Non-Termination Analysis of Linear Loop Programs with Condit...

引用

International Conference on Advanced Software Engineering and Its Applications

作者： Bi, Zhongqin Shan, Meijing Wu, Bin E China Normal Univ Shanghai Key Lab Trustworthy Comp Shanghai 200062 Peoples R China

ISBN: (纸本)9780769534329

Non-Termination analysis of loop programs plays a central role in many applications, especially in the field of safety critical softwares. This paper presents a method to analyze non-termination of linear programs with conditionals. We transform the linear loop programs with conditionals into the nested linear loop programs, and then check whether the inner loop terminates or not by the positive eigenvalues and their corresponding eigenvectors. If one of the inner loop in the nested linear loop is nonterminating, then the linear loop is nonterminating. Otherwise, we need to use ranking function or finite differences of expressions over transition systems to analyze the termination of the outer loop.

关键词： Linear Loop programs Non-Termination Analysis program Transform internal recycling program control structures Safety critical linear programming Finite differences Linear

来源：评论

学校读者我要写书评

暂无评论

Speculative parallelization

引用

COMPUTER 2006年第12期39卷 126-128页

作者： Gonzalez-Escribano, Arturo Llanos, Diego R. Univ Valladolid Dept Informat E-47002 Valladolid Spain

The most promising technique for automatically parallelizing loops when the system cannot determine dependences at compile time is speculative parallelization. Also called thread-level speculation, this technique assumes optimistically that the system can execute all iterations of a given loop in parallel. A hardware or software monitor divides the iterations into blocks and assigns them to different threads, one per processor, with no prior dependence analysis. If the system discovers a dependence violation at runtime, it stops the incorrectly computed work and restarts it with correct values. Of course, the more parallel the loop, the more benefits this technique delivers. To better understand how speculative parallelization works, it is necessary to distinguish between private and shared variables. Informally speaking, private variables are those that the program always modifies in each iteration before using them. On the other hand, values stored in shared variables are used in different iterations.

关键词： System Monitoring Multi Threading Parallelising Compilers program control structures Runtime Dependence Violation Discovery Speculative Parallelization Automatic Loop Parallelization program Compiler Thread Level Speculation Hardware Monitor Software Monitor program Dependence Analysis Hardware Monitoring Runtime Performance Loss Concurrent Computing Speculative Parallelization How Things Work

来源：评论

学校读者我要写书评

暂无评论

Optimizing intra-task voltage scheduling using data flow analysis 05

Optimizing intra-task voltage scheduling using data flow ana...

引用

10th Asia and South Pacific Design Automation Conference

作者： Shin, Dongkun Kim, Jihong Seoul Natl Univ Sch CSE Seoul 151742 South Korea

ISBN: (纸本)0780387368

Intra-task voltage scheduling (IntraDVS), which adjusts the supply voltage within an individual task boundary, is an effective technique for developing low-power applications. In IntraDVS, slack times are estimated by analyzing program's control flow information. In this paper, we propose an optimization technique for IntraDVS using data flow information. The proposed algorithm improves the energy efficiency by moving the voltage scaling points to earlier instructions based on the analysis results of program's data flow. The experimental results using an MPEG-4 encoder program show that the proposed algorithm reduces the energy consumption by 40-45% over the original IntraDVS algorithm.

关键词： data flow analysis program control structures optimisation image coding scheduling intra-task voltage scheduling data flow analysis IntraDVS supply voltage individual task boundary low-power applications slack times program control flow optimization technique MPEG-4 encoder program energy consumption

来源：评论

学校读者我要写书评

暂无评论

Using cornpiler-generated approximate critical path information to prioritise instructions for value prediction

引用

IEE PROCEEDINGS-COMPUTERS AND DIGITAL TECHNIQUES 2004年第5期151卷 321-331页

作者： Zhao, Q Lilja, DJ Sun Microsyst Inc Menlo Pk CA USA Univ Minnesota Dept Elect & Comp Engn Minneapolis MN 55455 USA Univ Minnesota Minnesota Supercomp Inst Minneapolis MN 55455 USA

One of the potential difficulties in developing cost-effective value prediction mechanisms is determining which instructions should be selected for prediction when the hardware resources are limited. The authors examine a compiler algorithm that statically assigns priorities to instructions using approximate critical path information to identify the best candidates for value prediction. This static priority information is encoded into the instructions and subsequently used by the hardware to choose the most critical instructions at run-time for value prediction. The algorithm is implemented in the GCC compiler and performance potential is evaluated using an extended version of the SimpleScalar processor simulator. Our results with the SPEC95 and SPEC2000 benchmark programs show that this approximate algorithm can effectively capture the critical path information to consistently improve the performance of a processor with a hybrid value predictor compared to using no information about the criticality of instructions. Furthermore, it is shown that using only four priority levels encoded into two instruction bits is sufficient to capture enough priority information to effectively use the value prediction hardware.

关键词： hybrid value predictor compiler generators compiler-generated critical path information Compilers, interpreters and other processors static priority assignment Parallel architecture program control structures SPEC95 benchmark instruction sets GCC compiler instruction prioritisation SimpleScalar processor simulator SPEC2000 benchmark approximate critical path information Performance evaluation and testing parallel architectures performance evaluation value prediction

来源：评论

学校读者我要写书评

暂无评论

Mathematical structure model for word-based program

引用

KNOWLEDGE-BASED SYSTEMS 2003年第7-8期16卷 399-411页

作者： Arai, O Fujita, H Iwate Prefectural Univ Fac Software & Informat Sci Takizawa Iwate 0200193 Japan CATENA Co Tokyo Japan

The new software world is progressing steadily forward but is not yet within range of where it needs to be. This paper presents a mathematical ground for the Lyee methodology, which has already produced several achievements in industry. This method enables us not to attention the sequential order of program execution. By introducing the concept of a state, it is possible to prove the program structure. The construction of such a program structure allows programmers to focus on conditions and formulae that calculate the value. Through this model, a system divided for catching correct requirements quickly is integrated, and its optimal program with minimum repetitions can be generated by rearranging words into the right order. (C) 2003 Published by Elsevier B.V.

关键词： program control structures system construction methodology intuition-based logic

来源：评论

学校读者我要写书评

暂无评论

Recurses!

引用

COMPUTING IN SCIENCE & ENGINEERING 2003年第3期5卷 76-81页

作者： Noble, JV Univ Virginia Charlottesville VA 22903 USA

THIS COLUMN IS ABOUT RECURSION: FUNCTIONS, SUBROUTINES, AND EVEN WHOLECOMPUTER LANGUAGES DEFINED IN TERMS OF THEMSELVES. RECURSION IS A DIRECT and elegant way totranslate certain mathematical relations into programs, and it's a great technique for discoveringefficient algorithms. Given its utility, you might wonder why people seldom use it. Here are justsome of the reasons why: 1. Not all computer languages permit recursion (although most do today).Recursion seems arcane to scientifiprogrammers of my generation who grew up with Fortran, whichforbade it. (Fortunately, Fortran 90 and later versions have remedied this.2. Not all languagesthat permit recursion make it easy, especially for nontextbook examples (as I recently learned whentranslating some algorithms to C). 3. Although useful, recursion is never essential: by theorem, arecursive algorithm can always be re-expressed nonre-cursively. 4. Recursive programs are generallybelieved to execute slower or to use more memory than their nonrecursive equivalents. Poor exampleshave reinforced this negative impression; ditto for languages that implement recursioninefficiently.

关键词： program control structures

来源：评论

学校读者我要写书评

暂无评论

Exploiting partial operand knowledge

Exploiting partial operand knowledge

引用

International Conference on Parallel Processing

作者： Mestan, BR Lipasti, MH IBM Corp IBM Microelect Austin TX 78758 USA

ISBN: (纸本)0769520170

Conventional microprocessor designs treat register operands as atomic units. In such designs, no portion of an operand may be consumed until the entire operand has been produced In practice, logic circuits and arithmetic units that generate some portion of an operand in advance of the remaining portions are both feasible and desirable, and have been employed in several existing designs. This paper examines existing and new approaches for exploiting early partial knowledge of an instruction input operands for overlapping the execution of dependent instructions and resolving unknown dependences. In particular we study three applications of partial operand knowledge: disambiguating loads from earlier stores, performing partial tag matching in set-associative caches, and resolving mispredicted conditional branches. We find that each of these is feasible with partial input operands. With the goal of fully exploiting this characteristic, we propose and evaluate a bit-sliced microarchitecture that decomposes a processor data path into 16- and 8-bit slices. We find that a bit-slice design using two 16-bit slices achieves IPC within 1% of an ideal design and attains a 16% speed-up over a conventional pipelined design not using partial operands.

关键词： pipeline processing instruction sets computer architecture program control structures logic circuits microprocessor design register operand instruction input operand dependent instruction partial operand knowledge tag matching set-associative cache conditional branch bit-sliced microarchitecture processor datapath IPC pipelined design

来源：评论

学校读者我要写书评

暂无评论

The expressive power of higher-order types or, life without CONS

引用

JOURNAL OF FUNCTIONAL programMING 2001年第1期11卷 55-94页

作者： Jones, ND Univ Copenhagen DIKU DK-1168 Copenhagen Denmark

Compare first-order functional programs with higher-order programs allowing functions as function parameters. Can the the first program class solve fewer problems than the second? The answer is no: both classes are Turing complete, meaning that they can compute all partial recursive functions. In particular, higher-order values may be first-order simulated by use of the list constructor 'cons' to build function closures. This paper uses complexity theory to prove some expressivity results about small programming languages that are less than Turing complete. Complexity classes of decision problems are used to characterize the expressive power of functional programming language features. An example: second-order programs are more powerful than first-order. since a function f of type [Boo1]-> Boo1 is computable by a cons-free first-order functional program if and only if f is in PTIME, whereas f is computable by a cons-free second-order program if and only if f is in EXPTIME. Exact characterizations are given for those problems of type [Boo1]-> Boo1 solvable by programs with several combinations of operations on data: presence or absence of constructors;the order of data values: 0, 1. or higher;and program control structures: general recursion, tail recursion, primitive recursion.

关键词： program control structures Functional programming higher-order complexity classes FIRST ORDER economic offence functional parameter Turing life instruction type Complexity theory If and only if Recursion program control

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：