矩形件无约束二维板材剪切的4块排样算法

针对矩形件无约束二维板材剪切排样问题,提出一种新的4块排样方式及其生成算法.该排样方式将板材划分成4个块,对每个块,按照递归方式进行排样.选择一行同种矩形件放置在块的左下角,沿着这行矩形件的上边界和右边界将该块剩余部分划分成两个更小的子块以待进一步递归考察.首先,构造动态规划算法一次性生成所有可能尺寸的块中矩形件的递归...     

Sequential/Parallel Matrix Array Languages

Abstract

A new system, that of matrix grammars, for two-dimensional pattern processing is introduced. Two hierarchies induced on Chomsky's are found and are compared with each other. Language operations such as union, catenation (row and column), Kleene's closure (row and column) and homomorphisms are investigated. It is found that the smallest class of these languages may serve as the class of regular arrays which is defined as the smallest class of arrays closed under union, catenation (row and column) and Kleene's closure (row and column). Eight possible ways of defining a matrix language are discussed and it is suggested that one of them may lead to a normal form of matrix grammers. The method is advantageous over others in several points. Perhaps the most interesting of all is that it provides a compromise between purely sequential methods which take too much time for large arrays and purely parallel methods which usually take too much hardware for large arrays.     

AES算法优化及其在ARM上的应用

提出一种高级加密标准(AES)算法的优化方案,适合在ARM处理器上运行长度均为128位的明文和密钥。将输入的明文和密钥按列优先原则排列成4×4的状态矩阵。对列混合、逆列混合以及密钥扩展进行优化,采用轮打开方式和轮不打开方式在S3C2440平台上实现该算法。结果表明,该算法可以在ARM上高效运行,并占用较少的ROM空间。     

Real-time reversible iterative arrays

Iterative arrays are one-dimensional arrays of interconnected interacting finite automata. The cell at the origin is equipped with a one-way read-only input tape. We investigate iterative arrays as acceptors for formal languages. In particular, we consider real-time devices which are reversible on the core of computation, i.e., from initial configuration to the configuration given by the time complexity. This property is called real-time reversibility. It is shown that real-time reversible iterative arrays can simulate restricted variants of stacks and queues. It turns out that real-time reversible iterative arrays are strictly weaker than real-time reversible cellular automata. On the other hand, a non-semilinear language is accepted. We show that real-time reversibility itself is not even semidecidable, which extends the undecidability for cellular automata and contrasts with the general case, where reversibility is decidable for one-dimensional devices. Moreover, we prove the non-semidecidability of several other properties. Several closure properties are also derived.     

Exploiting fine-grain parallelism on dataflow architectures

Although dataflow computers have many attractive features, skepticism exists concerning their efficiency in handling arrays (vectors) in high performance scientific computation. This paper outlines an efficient implementation scheme for arrays in applicative languages (such as VAL and SISAL) based on the principles of dataflow software pipelining. It illustrates how the fine-grain parallelism of dataflow approach can effectively handle large amount of data structured in applicative array operations. This is done through dataflow software pipelining between pairs of code blocks which act as producer-consumer of array values. To make effective use of the pipelined code mapping scheme, a compiler needs information concerning the overall program structure as well as the structure of each code block. An applicative language provides a basis for such analysis.

The program transformation techniques described here are developed primarily for the computationally intensive part of a scientific numerical program, which is usually formed by one or a few clusters of acyclic connected code blocks. Each code block defines an array value from several input arrays. We outline how mapping decisions of arrays can be based on a global analysis of attributes of the code blocks. We emphasize the role of overall program structure and the strategy of global optimization of the machine code structure. The structure of a proposed dataflow compiler based on the scheme described in this paper is outlined.     

Output String Languages of Compositions of Deterministic Macro Tree Transducers

The composition of total deterministic macro tree transducers gives rise to a proper hierarchy with respect to their output string languages (these are the languages obtained by taking the yields of the output trees). There is a language not in this hierarchy which can be generated by a (quite restricted) nondeterministic string transducer, namely, a two-way generalized sequential machine. Similar results hold for attributed tree transducers, for controlled EDT0L systems, and for YIELD mappings (which proves properness of the IO-hierarchy). Witnesses for the properness of the macro tree transducer hierarchy can already be found in the latter three hierarchies.     

PB-BLAS: a set of parallel block basic linear algebra subprograms

We propose a new software package which would be very useful for implementing dense linear algebra algorithms on block-partitioned matrices. The routines are referred to as block basic linear algebra subprograms (BLAS), and their use is restricted to computations in which one or more of the matrices involved consists of a single row or column of blocks, and in which no more than one of the matrices consists of an unrestricted two-dimensional array of blocks. The functionality of the block BLAS routines can also be provided by Level 2 and 3 BLAS routines. However, for non-uniform memory access machines the use of the block BLAS permits certain optimizations in memory access to be taken advantage of. This is particularly true for distributed memory machines, for which the block BLAS are referred to as the parallel block basic linear algebra subprograms (PB-BLAS). The PB-BLAS are the main focus of this paper, and for a block-cyclic data distribution, in a single row or column of blocks lies in a single row or column of the processor template. The PB-BLAS consist of calls to the sequential BLAS for local computations, and calls to the BLACS for communication. The PB-BLAS are the building blocks for implementing ScaLAPACK, the distributed-memory version of LAPACK, and provide the same ease-of-use and portability for ScaLAPACK that the BLAS provide for LAPACK. The PB-BLAS consist of all Level 2 and 3 BLAS routines for dense matrix computations (not for banded matrix) and four auxiliary routines for transposing and copying of a vector and/or a block vector. The PB-BLAS are currently available for all numeric data types, i.e., single and double precision, real and complex.     

On the complexity of nonuniform wavelength-based machine

The wavelength-based machine, or simply w-machine, is an optical computational model, which is designed based on simultaneous movement of several wavelengths in a single light ray, and simultaneous effect of simple optical devices on them. In this paper, we investigate nonuniform complexity classes of w-machine, based on three complexity measures, namely, size, time, and word length. We show that the class of languages which can be generated by constant size nonuniform w-machines contain infinitely many Turing undecidable languages. Also, we show that polynomial size nonuniform w-machines generate all NP languages, and every NP-hard language requires at least polynomial time and polynomial size nonuniform w-machines to be generated. We prove that the class of languages which can be generated by polynomial size nonuniform w-machines is equal to NP/poly, and almost all languages require exponential size and polynomial time nonuniform w-machines to be generated.     

Augmented tranśition networks and their relation to tree transducers

Augmented Transition Network Parsers (ATN) were defined by Woods and used by him in a natural language understanding system. Every recursively enumerable set is recognizable by an ATN.We define the Basic ATN, a limited class of ATN, and show that the languages accepted by this class are exactly those generated by a single top-down finite-state tree transducer, as defined by Rounds and Thatcher. These languages are known to be context-sensitive but have an NP-complete recognition problem.     

SoC芯片设计方法及标准化

随着集成电路技术的迅速发展，集成电路已进入系统级芯片（SoC)设计时代，SoC芯片的集成度越来越高，单芯片上的集成度和操作频率越来越高，投放市场的时间要求越来越短，为了实现这样的SoC芯片，设计越来越依赖IP模块的重用，SoC复杂性的提高和IP模块的多样化，SoC芯片中多个厂商不同IP模块的使用，导致了IP模块可重用的许多问题，IP模块和片上总线，以及EDA工具接口的标准化，是解决IP模块标准化的很好途径，另一方面，SoC芯片设计的复杂性和嵌入软件所占比重的增加，要求更高层次的系统抽象和软硬件的协同设计，使用更流地的设计进行系统的硬件设计和更有效的系统设计方法，描述了SoC芯片设计中的IP模块可重用技术以及所存在的问题，介绍了SoC IP模块和片上总线结构的标准化，讨论了基于C／C＋＋扩展类库的系统级描述语言和基于平台的SoC设计方法。     

On GID-Testable Two-Dimensional Iterative Arrays

A new approach is presented for easily testable two-dimensional iterative arrays.It is an improvement of GI-testability (Group Identical testability)and is referred to as GID-testability (Group Identical and Different testability).In a GID-testable two-dimensional array,the primary x and y outputs are organized into groups and every group has more than one output.This is similar to the GI-testable arrays.However,GID-testability not only ensures that identical test responses can be obtained from every output in the same group when an array is fault free,but also ensures that at least one output has different test responses (from the other outputs in a group)when a cell in the array is faulty.Therefore,all faults can be detected under the assumption of a single faulty cell model.It is proved that an arbitrary two-dimensional iterative array is GID-testable if seven x-states and seven y-states are added to the original flow table of the basic cell of the array.GID-testability simplifies the response verification of built-in-self-testing in a way similar to PI-and GI-testability^[6-9].Therefore,it is suitable for BIST design.     

On static output‐feedback stabilization for multi‐input multi‐output positive systems

This paper revisits the static output‐feedback stabilization problem for positive systems. We first point out that for a class of positive systems whose output matrix has a particular row echelon form, this problem can be completely solved via linear programming. By duality, the result is also valid when the column echelon form of the input matrix has a particular structure. Along this line, by augmenting the output matrix as well as the feedback gain matrix, an iterative convex optimization algorithm is developed for the more general case. Finally, we show that the proposed method has advantages over existing works via several numerical examples. Copyright © 2014 John Wiley & Sons, Ltd.     

Optimal tradeoffs for addition on systolic arrays

The complexity of adding twon-bit numbers on a two-dimensional systolic array is investigated. We consider different constraints on the systolic array, including:

whether or not the input and output ports lie on the periphery of the array,

constraints placed on the arrival and departure times of inputs and outputs

. For all combinations of the above constraints, we obtain optimal tradeoffs among the resources of area, pipeline delay, and worst-case time. It turns out that there is a subtle interplay among the constraints and some of our results seem counterintuitive. For instance, we show that allowing more-significant bits to arrive earlier than less-significant bits can speed up addition by a factor of logn. We also show that multiplexing can often result in a smaller array. On the other hand, we show that some known results, such as Chazelle and Monier's bounds for arrays that have input/output ports on the perimeter, also hold in less constrained models.     

Typechecking for XML transformers

We study the typechecking problem for XML (eXtensible Markup Language) transformers: given an XML transformation program and a DTD for the input XML documents, check whether every result of the program conforms to a specified output DTD. We model XML transformers using a novel device called a k-pebble transducer, that can express most queries without data-value joins in XML-QL, XSLT, and other XML query languages. Types are modeled by regular tree languages, a robust extension of DTDs. The main result of the paper is that typechecking for k-pebble transducers is decidable. Consequently, typechecking can be performed for a broad range of XML transformation languages, including XML-QL and a fragment of XSLT.     

Compiling Array Expressions for Efficient Execution on Distributed-Memory Machines

Array statements are often used to express data-parallelism in scientific languages such as Fortran 90 and High Performance Fortran. In compiling array statements for a distributed-memory machine, efficient generation of communication sets and local index sets is important. We show that for arrays distributed block-cyclically on multiple processors, the local memory access sequence and communication sets can be efficiently enumerated as closed forms using regular sections. First, closed form solutions are presented for arrays that are distributed using block or cyclic distributions. These closed forms are then used with avirtual processor approachto give an efficient solution for arrays with block-cyclic distributions. This approach is based on viewing a block-cyclic distribution as a block (or cyclic) distribution on a set of virtual processors, which are cyclically (or block-wise) mapped to physical processors. These views are referred to asvirtual-blockorvirtual-cyclicviews, depending on whether a block or cyclic distribution of the array on the virtual processors is used. The virtual processor approach permits different schemes based on the combination of the virtual processor views chosen for the different arrays involved in an array statement. These virtualization schemes have different indexing overhead. We present a strategy for identifying the virtualization scheme which will have the best performance. Performance results on a Cray T3D system are presented for hand-compiled code for array assignments. These results show that using the virtual processor approach, efficient code can be generated for execution of array statements involving block-cyclically distributed arrays.     

Playware technology for physically activating play

We present and use the robotic building block concept to create playware. Playware is the use of intelligent technology to create the kinds of leisure activity we normally label play, i.e., intelligent hard- and software that aims at producing play and playful experiences among users. The technological concept of physical building blocks with processing, input, and output (including communication) is derived from embodied artificial intelligence that emphasizes the role of interplay between morphology and control. We exemplify the building block concept with the tangible tiles that we created as components for a new kind of playground on which children can experience immediate feedback on their motions. Hence, this kind of playground allows the implementation of games and plays that demand physical activity amongst the users, and thereby contribute as a new tool in the fight against obesity. The tangible tiles are homogenous building blocks, which gives assembly, substitution, and production advantages. However, we may also create a system of heterogeneous building blocks, e.g., by adding special-purpose tiles such as loud-speaker tiles. We performed tests with the tangible tiles placed at a school for 2 months' continuous use.     

The complexity of the membership problem for some extensions of context-free languagest†

The time and tape complexity of some families of languages defined in the literature by altering methods of generation by context-free grammars is considered. Specifically; it is shown that the following families of languages can be recognized by deterministic multitape Turing machines either in polynomial time or within (log n)² tape:

1) the context independent developmental (EOL) languages;

2) the simple matrix languages;

3) the languages generated by derivation restricted state grammars.:

4) the languages generated by linear context-free grammars with certain non-regular control sets;

5) the languages generated by certain classes of vector grammars.

In fact, these languages are of the same tape complexity as context-free languages. Other results indicate the complexity of EDOL languages and the effects on complexity of applying the homomorphic replication operator to regular and context-free languages.     

On the complexity of formal grammars

Summary The time and space complexity of the class of languages generated in linear time by context-sensitive grammars is investigated. Among other results it is shown that the membership question for languages in the class is NP-complete.This research was supported in part by the National Science Foundation under Grants DCR75-15945 and MCS77-11360     

Modelling and recognition of the linguistic components in American Sign Language

The manual signs in sign languages are generated and interpreted using three basic building blocks: handshape, motion, and place of articulation. When combined, these three components (together with palm orientation) uniquely determine the meaning of the manual sign. This means that the use of pattern recognition techniques that only employ a subset of these components is inappropriate for interpreting the sign or to build automatic recognizers of the language. In this paper, we define an algorithm to model these three basic components form a single video sequence of two-dimensional pictures of a sign. Recognition of these three components are then combined to determine the class of the signs in the videos. Experiments are performed on a database of (isolated) American Sign Language (ASL) signs. The results demonstrate that, using semi-automatic detection, all three components can be reliably recovered from two-dimensional video sequences, allowing for an accurate representation and recognition of the signs.