On the number of nodes in universal networks of evolutionary processors

We consider the networks of evolutionary processors (NEP) introduced by J. Castellanos, C. Martí n-Vide, V. Mitrana and J. Sempere recently. We show that every recursively enumerable (RE) language can be generated by an NEP with three nodes modulo a terminal alphabet and moreover, NEPs with four nodes can generate any RE language. Thus, we improve existing universality result from five nodes down to four nodes. For mNEPs (a variant of NEPs where operations of different kinds are allowed in the same node) we obtain optimal results: each RE language can be generated by an mNEP with one node modulo a terminal alphabet, and mNEPs with two nodes can generate any RE language; this is not possible for mNEPs with one node. Some open problems are formulated.     

Hybrid networks of evolutionary processors are computationally complete

A hybrid network of evolutionary processors (an HNEP) consists of several language processors which are located in the nodes of a virtual graph and able to perform only one type of point mutations (insertion, deletion, substitution) on the words found in that node, according to some predefined rules. Each node is associated with an input and an output filter, defined by some random-context conditions. After applying in parallel a point mutation to all the words existing in every node, the new words which are able to pass the output filter of the respective node navigate simultaneously through the network and enter those nodes whose input filter they are able to pass. We show that even the so-called elementary HNEPs are computationally complete. In this case every node is able to perform only one instance of the specified operation: either an insertion, or a deletion, or a substitution of a certain symbol. We also prove that in the case of non-elementary networks, any recursively enumerable language over a common alphabet can be obtained with an HNEP whose underlying structure is a fixed graph depending on the common alphabet only.Received: 19 July 2004, Published online: 19 January 2005Erzsébet Csuhaj-Varjú: Work supported in part by a grant from the NATO Scientific Committee in Spain and the Hungarian Scientific Research Fund OTKA Grant No. T 042529Victor Mitrana: Work supported by the Centre of Excellence in Information Technology, Computer Science and Control, ICA1-CT-2000-70025, HUN-TING project, WP5.     

Deep, narrow sigmoid belief networks are universal approximators

In this note, we show that exponentially deep belief networks can approximate any distribution over binary vectors to arbitrary accuracy, even when the width of each layer is limited to the dimensionality of the data. We further show that such networks can be greedily learned in an easy yet impractical way.     

Coset networks as connectors in parallel processors

An active area of research regarding parallel computer systems deals with the design of interconnection networks. Among all interconnection networks, permutation networks play a special role as all other networks can be constructed using such networks. It was recently shown that many permutation networks reported in the literature are manifestations of coset decompositions of symmetric groups. This result is generalized here to obtain several other previously unknown permutation networks which satisfy such decompositions. In addition, analyses of the edge-count, propagation delay, fan-out, and setup time of such networks are provided. The results lead to some anomolous behavior as well as several trade-offs among these parameters. For example, it is shown that a complete bipartite graph is the fastest and most economical direct realization of a permutation network. Furthermore, it is shown that the fan-out of a network is inversely proportional to the propagation delay whereas the setup time may or may not relate to the propagation delay at all depending on the network in question. Finally, two constant fan-out implementations of these networks using O (n ^1.59) 2 × 1 multiplexers and 2 × 2 switches are presented.This work is supported in part by the National Science Foundation under Grant No: CCR-8708864.     

Oblivious algorithms for multicores and networks of processors

We address the design of algorithms for multicores that are oblivious to machine parameters. We propose HM, a multicore model consisting of a parallel shared-memory machine with hierarchical multi-level caching, and we introduce a multicore-oblivious approach to algorithms and schedulers for HM. A multicore-oblivious algorithm is specified with no mention of any machine parameters, such as the number of cores, number of cache levels, cache sizes and block lengths. However, it is equipped with a small set of instructions that can be used to provide hints to the run-time scheduler on how to schedule parallel tasks. We present efficient multicore-oblivious algorithms for several fundamental problems including matrix transposition, FFT, sorting, the Gaussian Elimination Paradigm, list ranking, and connected components. The notion of a multicore-oblivious algorithm is complementary to that of a network-oblivious algorithm, introduced by Bilardi et al. (2007)  [8] for parallel distributed-memory machines where processors communicate point-to-point. We show that several of our multicore-oblivious algorithms translate into efficient network-oblivious algorithms, adding to the body of known efficient network-oblivious algorithms.     

Quantization of deep neural networks for accumulator-constrained processors

We introduce an Artificial Neural Network (ANN) quantization methodology for platforms without wide accumulation registers. This enables fixed-point model deployment on embedded compute platforms that are not specifically designed for large kernel computations (i.e. accumulator-constrained processors). We formulate the quantization problem as a function of accumulator size, and aim to maximize the model accuracy by maximizing bit width of input data and weights. To reduce the number of configurations to consider, only solutions that fully utilize the available accumulator bits are being tested. We demonstrate that 16 bit accumulators are able to obtain a classification accuracy within 1% of the floating-point baselines on the CIFAR-10 and ILSVRC2012 image classification benchmarks. Additionally, a near-optimal 2 × speedup is obtained on an ARM processor, by exploiting 16 bit accumulators for image classification on the All-CNN-C and AlexNet networks.     

Mapping Datalog program execution to networks of processors

The problem of mapping the parallel bottom up execution of Datalog programs to an interconnected network of processors is studied. The parallelization is achieved by using hash functions that partition the set of instantiations for the rules. We first examine this problem in an environment where the number of processors and the interconnection topology is known, and communication between program segments residing at non-adjacent processors is not permitted. An algorithm is presented that decides whether a given Datalog program can be mapped onto such an architecture. We then relax the constraint on the architecture by allowing program segments residing at non-adjacent processors to communicate, A theory of approximate mappings is developed, and an algorithm to obtain the closest approximate mapping of a given Datalog program onto a given architecture is presented     

Large processors are good in VLSI chips

We show that any circuit modeled by an N-node graph of O(N^α) separator (α > $\text{1}\text{2}$) can be laid out in O(N^2α) area, even if each processing element occupies O(N^2α-1) area. When α = $\text{1}\text{2}$, with each processing element being O(log²N) area, it can still be laid out in O(N log²N) area.     

Coupled cluster algorithms for networks of shared memory parallel processors

As the popularity of using SMP systems as the building blocks for high performance supercomputers increases, so too increases the need for applications that can utilize the multiple levels of parallelism available in clusters of SMPs. This paper presents a dual-layer distributed algorithm, using both shared-memory and distributed-memory techniques to parallelize a very important algorithm (often called the “gold standard”) used in computational chemistry, the single and double excitation coupled cluster method with perturbative triples, i.e. CCSD(T). The algorithm is presented within the framework of the GAMESS [M.W. Schmidt, K.K. Baldridge, J.A. Boatz, S.T. Elbert, M.S. Gordon, J.J. Jensen, S. Koseki, N. Matsunaga, K.A. Nguyen, S. Su, T.L. Windus, M. Dupuis, J.A. Montgomery, General atomic and molecular electronic structure system, J. Comput. Chem. 14 (1993) 1347–1363]. (General Atomic and Molecular Electronic Structure System) program suite and the Distributed Data Interface [M.W. Schmidt, G.D. Fletcher, B.M. Bode, M.S. Gordon, The distributed data interface in GAMESS, Comput. Phys. Comm. 128 (2000) 190]. (DDI), however, the essential features of the algorithm (data distribution, load-balancing and communication overhead) can be applied to more general computational problems. Timing and performance data for our dual-level algorithm is presented on several large-scale clusters of SMPs.     

On the size of computationally complete hybrid networks of evolutionary processors

A hybrid network of evolutionary processors (an HNEP) is a graph where each node is associated with an evolutionary processor (a special rewriting system), a set of words, an input filter and an output filter. Every evolutionary processor is given with a finite set of one type of point mutations (an insertion, a deletion or a substitution of a symbol) which can be applied to certain positions of a string over the domain of the set of these rewriting rules. The HNEP functions by rewriting the words that can be found at the nodes and then re-distributing the resulting strings according to a communication protocol based on a filtering mechanism. The filters are defined by certain variants of random-context conditions. HNEPs can be considered as both language generating devices (GHNEPs) and language accepting devices (AHNEPs). In this paper, by improving the previous results, we prove that any recursively enumerable language can be determined by a GHNEP and an AHNEP with 7 nodes. We also show that the families of GHNEPs and AHNEPs with 2 nodes are not computationally complete.     

Complexity-preserving simulations among three variants of accepting networks of evolutionary processors

In this paper we consider three variants of accepting networks of evolutionary processors. It is known that two of them are equivalent to Turing machines. We propose here a direct simulation of one device by the other. Each computational step in one model is simulated in a constant number of computational steps in the other one while a translation via Turing machines squares the time complexity. We also discuss the possibility of constructing simulations that preserve not only complexity, but also the shape of the simulated network.     

Computational completeness of complete,star-like,and linear hybrid networks of evolutionary processors with a small number of processors

A hybrid network of evolutionary processors (HNEP) is a graph where each node is associated with a special rewriting system called an evolutionary processor, an input filter, and an output filter. Each evolutionary processor is given a finite set of one type of point mutations (insertion, deletion or a substitution of a symbol) which can be applied to certain positions in a string. An HNEP rewrites the strings in the nodes and then re-distributes them according to a filter-based communication protocol; the filters are defined by certain variants of random-context conditions. HNEPs can be considered both as languages generating devices (GHNEPs) and language accepting devices (AHNEPs); most previous approaches treated the accepting and generating cases separately. For both cases, in this paper we show that five nodes are sufficient to accept (AHNEPs) or generate (GHNEPs) any recursively enumerable language by showing the more general result that any partial recursive relation can be computed by an HNEP with (at most) five nodes with the underlying graph structure for the communication between the evolutionary processors being the complete or the linear graph with five nodes, whereas with a star-like communication graph we need six nodes. If the final results are defined by only taking the terminal strings out of the designated output node, then for these extended HNEPs we can prove that only four nodes are needed in all cases—for computing any partial recursive relation as well as for generating and accepting any recursively enumerable language—and the underlying communication structure can be a complete or a linear graph, but now even a star-like graph, too.     

User-centric universal multimedia access in home networks

Much research is currently being conducted towards Universal Multimedia Access, aiming at removing barriers that arise when multimedia content is to be consumed with more and more heterogeneous devices and over diverse networks. We argue that users should be put at the center of the research work to enable user-centric multimedia access. In this paper we present the requirements for a user-centric multimedia access system in a networked home environment. These requirements are easy access to available content repositories, context awareness, content adaptation and session migration. After showing the limits of state-of-the-art technologies, we present the architecture of a system which allows unified access to the home network content, automatically delivered to rendering devices close to the user, adapted according to the rendering device constraints, and which is also capable of session mobility.     

Evaluation of robust control by universal learning networks

The characteristics of control system design using a universal learning network (ULN) are such that both the controlled systems and their controller are represented in a unified framework, and that the learning stage of the ULN can be executed by using not only first-order derivatives (gradient) but also the higher order derivatives of the criterion function with respect to parameters. ULNs have the same generalization ability as neural networks. So the ULN controller is able to control the system in a favorable way under an environment which is little different from the environment of the control system at the learning stage. However, stability cannot be sufficiently realized. In this paper, we propose a robust control method using a ULN and second-order derivatives of that ULN. Robust control, as considered here, is defined as follows. Even though the initial values of the node outputs are very different from those at the learning stage, the control system is able to reduce its influence to other node outputs and can control the system as in the case of no variation. In order to realize such robust control, a new term concerning the variation is added to the usual criterion function, and the parameters are adjusted so as to minimize the above-mentioned criterion function using second-order derivatives of the criterion function with respect to the parameters. Finally, it is shown that the ULN controller constructed by the proposed method works effectively in a simulation study of a non-linear crane system. This work was presented, in part, at the International Symposium on Artificial Life and Robotics, Oita, Japan, February 18–20, 1996     

The role of evolutionary operations in accepting hybrid networks of evolutionary processors

In this paper, we investigate the role of evolutionary operations in accepting hybrid networks of evolutionary processors (AHNEP for short) in the following way. We consider AHNEPs with all the nodes specialized in only one evolutionary operation (substitution, insertion, or deletion) or in two operations out of these three. The considered variants differ in two respects: filters that are used to control the exchange of information (we use random context conditions and regular languages as filters) and the way of accepting the input word (at least one output node or all output nodes are non-empty at some moment in the computation). The computational power of all these variants is studied.