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

Actor-oriented design of embedded hardware and software systems

JOURNAL OF CIRCUITS SYSTEMS AND COMPUTERS 2003年第3期12卷 231-260页

作者： Lee, EA Neuendorffer, S Wirthlin, MJ Univ Calif Berkeley Dept EECS Berkeley CA 94720 USA Brigham Young Univ ECEN Dept Provo UT 84602 USA

In this paper, we argue that model-based design and platform-based design are two views of the same thing. A platform is an abstraction layer in the design flow. For example, a core-based architecture and an instruction set architecture are platforms. We focus on the set of designs induced by this abstraction layer. For example, the set of all ASICs based on a particular core-based architecture and the set of all x86 programs axe induced sets. Hence, a platform is equivalently a set of designs. Model-based design is about using platforms with useful modeling properties to specify designs, and then synthesizing implementations from these specifications. Hence model-based design is the view from above (more abstract, closer to the problem domain) and platform-based design is the view from below (less abstract, closer to the implementation technology). One way to define a platform is to provide a design language. Any valid expression in the language is an element of the set. A platform provides a set of constraints together with known tradeoffs that flow from those constraints. Actor-oriented platforms, such as Simulink, abstract aspects of program-level platforms, such as Java, C++, and VHDL. Actor-oriented platforms orthogonalize the actor definition language and the actor composition language, enabling highly polymorphic actor definitions and design using multiple models of computation. In particular, we concentrate on the use of constrained models of computation in design. The modeling properties implied by well chosen constraints allow more easily understood designs and are preserved during synthesis into program-level descriptions. We illustrate these concepts by describing a design framework built on Ptolemy II.

关键词： actor-oriented design embedded systems model-based design models of computation platform-based design synthesis Ptolemy II JHDL

来源：评论

学校读者我要写书评

暂无评论

Memoryless computation: New results, constructions, and extensions

引用

THEORETICAL COMPUTER SCIENCE 2015年第C期562卷 129-145页

作者： Gadouleau, Maximilien Riis, Soren Univ Durham Sch Engn & Comp Sci Durham DH1 3LE England Queen Mary Univ London Sch Elect Engn & Comp Sci London E1 4NS England

In this paper, we are interested in memoryless computation, a modern paradigm to compute functions which generalises the famous XOR swap algorithm to exchange the contents of two variables without using a buffer. In memoryless computation, programs are only allowed to update one variable at a time. We first consider programs which do not use any memory. We study the maximum and average number of updates required to compute functions without memory. We then derive the exact number of instructions required to compute any manipulation of variables. This shows that combining variables, instead of simply moving them around, not only allows for memoryless programs, but also yields shorter programs. Second, we show that allowing programs to use memory is also incorporated in the memoryless computation framework. We then quantify the gains obtained by using memory: this leads to shorter programs and allows us to use only binary instructions, which is not sufficient in general when no memory is used. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Memoryless computation models of computation computational difficulty Symmetric group Theory of data Combinatorics

来源：评论

学校读者我要写书评

暂无评论

SEPARATION BETWEEN DETERMINISTIC AND RANDOMIZED QUERY COMPLEXITY

引用

SIAM JOURNAL ON COMPUTING 2018年第4期47卷 1644-1666页

作者： Mukhopadhyay, Sagnik Radhakrishnan, Jaykumar Sanyal, Swagato KTH Royal Inst Technol Stockholm Sweden Tata Inst Fundamental Res Bombay Maharashtra India IIT Kharagpur Dept Comp Sci & Engn Kharagpur W Bengal India

Saks and Wigderson 27th FOGS, IEEE Computer Society, as Alamitos, CA, 1986, pp. 29-38] conjectured that R-0(f) = Omega (D(f)(0.753...)) for all Boolean functions f, here R-0 denotes the randomized complexity and D denotes 10 determinist is query CCATI p1exit;,yr. We,show t hat for the pointer function GPW(rxs) defined by Goos. Pitassi, arid Watson [in Proceedings of the 56th FOCS, IEEE, Piscataway, NJ, 2015, pp. 1077-1088] the following hold: s) s) and (b) R-1(GPW(rxs)) = Irs), cyhere R1 denotes the randomized one-sided error query complexity. These results imply that (i) R-0(GPW(s2xs)) = O(D(GPW(s2xs))2/3) t hereby refuting the;conjecture of Saks and Wigdorson, and (ii) R-1 (GPW(sxs))- O(R-0(GPW(sxs))(2/3)), thereby providing a polynomial separation between the randomized zero -error and one-sided error query complexity measures.

关键词： deterministic decision tree randomized decision tree query complexity models of computation

来源：评论

学校读者我要写书评

暂无评论

Logical Synchrony Networks: A Formal Model for Deterministic Distribution

引用

IEEE ACCESS 2024年 12卷 80872-80883页

作者： Kenwright, Logan Roop, Partha Allen, Nathan Lall, Sanjay Cascaval, Calin Spalink, Tammo Izzard, Martin Univ Auckland Dept Elect Comp & Software Engn Auckland 1010 New Zealand Stanford Univ Dept Elect Engn Stanford CA 94305 USA Google Res Mountain View CA 94043 USA

In the modelling of distributed systems, most Model of computations (MoCs) rely on blocking communication to preserve determinism. A prominent example is Kahn Process Networks (KPNs), which supports non-blocking writes and blocking reads, and its implementable variant Finite FIFO Platforms (FFPs) which enforces boundedness using blocking writes. An issue with these models is that they mix process synchronisation with process execution, necessitating frequent blocking during synchronisation. This paper explores a recent alternative called bittide, which decouples the execution of a process from the synchronisation behaviour. Determinism and boundedness is preserved while enabling pipelined execution for better throughput. To understand the behaviour of these systems we define a formal model - a deterministic MoC called Logical Synchrony Networks (LSNs). LSNs describes a network of processes modelled as a graph, with edges representing invariant logical delays between a producer process and the corresponding consumer process. We show that this abstraction is satisfied by the KPN model, and subsequently by both the concrete FFPs and bittide architectures. Thus, we show that FFPs and bittide offer two ways of implementing deterministic distributed systems, with the latter being more performant.

关键词： Synchronization computational modeling Protocols Delays Hardware Computer architecture Distributed computing Distributed systems models of computation Kahn process networks bittide

来源：评论

学校读者我要写书评

暂无评论

Wang's B machines are efficiently universal, as is Hasenjaeger's small universal electromechanical toy

引用

JOURNAL OF COMPLEXITY 2014年第5期30卷 634-646页

作者： Neary, Turlough Woods, Damien Murphy, Niall Glaschick, Rainer Univ Zurich Inst Neuroinformat Zurich Switzerland ETH Zurich Switzerland CALTECH Pasadena CA 91125 USA Univ Politecn Madrid Fac Informat E-28040 Madrid Spain UPM UCM CEI Moncloa Madrid Spain Microsoft Res Cambridge CBI 2FB England

In the 1960s Gisbert Hasenjaeger built Turing Machines from electromechanical relays and uniselectors. Recently, Glaschick reverse engineered the program of one of these machines and found that it is a universal Turing machine. In fact, its program uses only four states and two symbols, making it a very small universal Turing machine. (The machine has three tapes and a number of other features that are important to keep in mind when comparing it to other small universal machines.) Hasenjaeger's machine simulates Hao Wang's B machines, which were proved universal by Wang. Unfortunately, Wang's original simulation algorithm suffers from an exponential slowdown when simulating Turing machines. Hence, via this simulation, Hasenjaeger's machine also has an exponential slowdown when simulating Turing machines. In this work, we give a new efficient simulation algorithm for Wang's B machines by showing that they simulate Turing machines with only a polynomial slowdown. As a second result, we find that Hasenjaeger's machine also efficiently simulates Turing machines in polynomial time. Thus, Hasenjaeger's machine is both small and fast. In another application of our result, we show that Hooper's small universal Turing machine simulates Turing machines in polynomial time, an exponential improvement. (C) 2014 Elsevier Inc. All rights reserved.

关键词： Polynomial time computational complexity Small universal Turing machines Wang's B machine Non-erasing Turing machines models of computation

来源：评论

学校读者我要写书评

暂无评论

Properties of probabilistic pushdown automata

引用

THEORETICAL COMPUTER SCIENCE 1998年第1期207卷 117-130页

作者： Macarie, II Ogihara, M Millennium Comp Corp Res & Adv Dev Grp Pittsford NY 14534 USA Univ Rochester Dept Comp Sci Rochester NY 14627 USA

Properties of (unbounded-error) probabilistic as well as "probabilistic plus nondeterministic" pushdown automata and auxiliary pushdown automata are studied. These models are analogous to their counterparts with nondeterministic and alternating states. Complete characterizations in terms of well-known complexity classes are given for the classes of languages recognized by polynomial time-bounded, logarithmic space-bounded auxiliary pushdown automats with probabilistic states and with "probabilistic plus nondeterministic" states. Also, complexity lower bounds are given for the classes of languages recognized by these automata with unlimited running time. It follows that, by fixing an appropriate mode of computation, the difference between classes of languages such as P and PSPACE, NL and SAC(1), PL and Diff(>)(#SAC(1)) is characterized as the difference between the number of stack symbols;that is, whether the stack alphabet contains one versus two distinct symbols. (C) 1998-Elsevier Science B.V. All rights reserved.

关键词： pushdown automata probabilistic computation models of computation space-bounded computation Arthur-Merlin games games against nature

来源：评论

学校读者我要写书评

暂无评论

Analysis of billiard ball computation using phase space logics

引用

PHYSICA D 1998年第1-2期120卷 236-252页

作者： Westmoreland, M Krone, J Schumacher, B Denison Univ Dept Comp Sci Granville OH 43023 USA Denison Univ Dept Math Granville OH 43023 USA Kenyon Coll Dept Phys Gambier OH 43022 USA

When analyzing individual gates in circuitry, one usually assumes that inputs are either 0 or 1, as are the outputs, but the fact is that these input values are really either "high" voltage or "low" voltage. Determining whether or not a given input is to be considered as high or low depends on a physical measurement of the voltage. Since physical measurement is never exact, it is more realistic to consider "high," "low," and "indeterminate," hence considering three possible values, rather than two, when reasoning about computer hardware. When considering physical measurement as part of the determination as to what inputs and outputs are for a given gate, one can no longer reason about these gates using boolean logic. There are several possible non-boolean alternatives one may consider. We will examine motivation for some such alternatives and point out how we might apply them to a particular model of computation: the billiard ball model. (C) 1998 Elsevier Science B.V. All rights reserved.

关键词： models of computation non-standard logics

来源：评论

学校读者我要写书评

暂无评论

On the number of zero-patterns of a sequence of polynomials

引用

JOURNAL OF THE AMERICAN MATHEMATICAL SOCIETY 2001年第3期14卷 717-735页

作者： Rónyai, L Babai, L Ganapathy, MK Hungarian Acad Sci Comp & Automat Res Inst H-1111 Budapest Hungary Univ Chicago Dept Comp Sci Chicago IL 60637 USA

Let f=(f1,...,fm) be a sequence of polynomials of degree ≤d in n variables (m≥n) over a field F. The zero-pattern of f at u∈F^n is the set of those i 1≤i≤m ) for which fi(u)=0. Let ZF(f) denote the number of zero-patterns of f as u ranges over F^n. We prove that ZF(f)≤Σj=0^n(j^m) for d=1 and (*) ZF(f) ≤ (n^(md))for d≥2. For m≥nd, these bounds are optimal within a factor of (7.25)^n. The bound (*) improves the bound (1+md)^n proved by J. Heintz (1983) using the dimension theory of affine varieties. Over the field of real numbers, bounds stronger than Heintz's but slightly weaker than (*) follow from results of J. Milnor (1964), H.E. Warren (1968), and others; their proofs use techniques from real algebraic geometry. In contrast, our half-page proof is a simple application of the elementary ``linear algebra bound''. Heintz applied his bound to estimate the complexity of his quantifier elimination algorithm for algebraically closed fields. We give several additional applications. The first two establish the existence of certain combinatorial objects. Our first application, motivated by the ``branching program'' model in the theory of computing, asserts that over any field F, most graphs with υ vertices have projective dimension Ω((υ/logυ)^1/2) (the implied constant is absolute). This result was previously known over the reals (Pudlák-Rodl). The second application concerns a lower bound in the span program model for computing Boolean functions. The third application, motivated by a paper by N. Alon, gives nearly tight Ramsey bounds for matrices whose entries are defined by zero-patterns of a sequence of polynomials. We conclude the paper with a number of open problems.

关键词： polynomials zero-patterns linear algebra bound sign-patterns real algebraic geometry affine varieties algebraically closed fields quantifier elimination asymptotic counting counting patterns graph representation projective dimension of graphs probabilistic method nonconstructive proof Ramsey theory models of computation span-programs extremal combinatorics

来源：评论

学校读者我要写书评

暂无评论

TOWARD A MODEL FOR BACKTRACKING AND DYNAMIC PROGRAMMING

引用

computationAL COMPLEXITY 2011年第4期20卷 679-740页

作者： Alekhnovich, Michael Borodin, Allan Buresh-Oppenheim, Joshua Impagliazzo, Russell Magen, Avner Pitassi, Toniann Inst Adv Study Sch Math Princeton NJ 08540 USA Univ Toronto Dept Comp Sci Toronto ON Canada Akamai Technol Cambridge MA USA Univ Calif San Diego CSE Dept San Diego CA 92103 USA

We propose a model called priority branching trees (pBT) for backtracking and dynamic programming algorithms. Our model generalizes both the priority model of Borodin, Nielson and Rackoff, as well as a simple dynamic programming model due to Woeginger, and hence spans a wide spectrum of algorithms. After witnessing the strength of the model, we then show its limitations by providing lower bounds for algorithms in this model for several classical problems such as Interval Scheduling, Knapsack and Satisfiability.

关键词： Greedy algorithms dynamic programming models of computation lower bounds

来源：评论

学校读者我要写书评

暂无评论

SIMULATION, REDUCTION AND PRESERVATION OF CORRECTNESS PROPERTIES OF PARALLEL SYSTEMS

引用

INFORMATION PROCESSING LETTERS 1983年第1期17卷 21-27页

作者： TIRRI, HR Department of Computer Science University of Helsinki SF-00250 Helsinki 25 Finland

A unified formal treatment of simulation and reduction concepts for parallel computation systems is presented. A computation homomorphism, as introduced by Kasai and Miller (1979), is used to study the correctness properties of parallel computation systems. The model for an asynchronous parallel system is presented, and the correctness properties to be studied are defined. It is shown that surjective homomorphism preserves all the correctness properties studied in Berthelot, Roucairol, and Valk (1979). The concepts of simulation and reduction are then studied, and a new definition of reduction induced by a surjective homomorphism is presented. Finally, the use of reduction in correctness proofs of parallel computation systems is investigated, and reduction is combined with recently developed verification techniques based on temporal logic.

关键词： models of computation simulation reduction correctness of parallel systems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：