Design and implementation of dual processor block with shared external cache memory

The availability of low cost, high performance microprocessors has led to various designs of shared memory multiprocessor systems. As a result, commercial products which are based on shared memory have been proliferated. Such a multiprocessor system is heavily influenced by the structure of memory system and it is not difficult to find that most configurations include local cache memories. The more processors a system carries, the larger local cache memory is needed to maintain the traffic to and from the shared memory at reasonable level. The implementation of local cache memories, however, is not a simple task because of environmental limitations. In particular, the general lack of board space availability presents a formidable problem. A cache memory system usually needs space mostly to support its complex control logic circuits for the cache itself and network interfaces like snooping logic circuits for shared bus. Although packaging can be made denser to reduce system size, there are still multiple processors per board. It requires a more area-efficient cache memory architecture. This paper presents a design of shared cache for dual processor board of bus-based symmetric multiprocessors. The design and implementation issues are described first and then the evaluation and measurement results are discussed. The shared cache proposed in this paper has been determined to be quite area-efficient without the significant loss of throughput and scalability. It has been implemented as a plug-in unit for TICOM, a prevalent commercial multiprocessor system.     

一种支持线索迁移的分布式存储结构

本文介绍一种基于ＵＮＩＸ的分布式存储结构，用于支持分布多系统中的机间线索迁移，同一地址空间中的多个线索实现为共享地址空间的多个轻权进程，这些进程核心视为普通的ＵＮＩＸ进程，本文主要讨论分式存储和线索迁移的实现机制。     

粘贴DNA计算模型的几种分子逻辑门的实现

理论上来说,基于DNA的分子逻辑门是DNA计算机体系结构的产生基础和DNA计算机实现技术的硬件基础。在这篇论文中,我们在先前提出的基于粘贴DNA计算模型的分子逻辑与门的实现方法的基础上,进一步提出了基于粘贴DNA计算模型的分子逻辑或门和与非门的实现方法。与先前方法类似,逻辑门、输入信号和输出信号是DNA分子。可以实现OR,NOT和NAND类型的逻辑门操作。需要使用包括聚合酶链反应(PCR),琼脂糖凝胶电泳,探针的标记与检测等生物工程技术。这些技术集成于DNA芯片中可用于DNA计算机的研制。     

实时分布式操作系统中共享对象通信模型的实现

与消息传递、远程过程调用和共享内存等进程间通信模型相比,在分布式存储多处理器上实现的共享对象模型能更自然、更高效地描述进程间的相互作用。它通过共享对象消除了各结点之间的物理边界,为系统提供了一种透明的分布式处理能力。这样,整个系统（包括硬件和软件）在逻辑上成为一个单系统。该模型已在仪器用弱实时分布式操作系统（ＩＯＷＲＴＤＯＳ）的全局共享对象（ＧＳＯ）层上实现。文中研究了共享对象通信模型,并详细讨论     

Machine independent AND and OR parallel execution of logicprograms. I. The binding environment

We describe a binding environment for the AND and OR parallel execution of logic programs that is suitable for both shared and nonshared memory multiprocessors. The binding environment was designed with a view of rendering a compiler using this binding environment machine independent. The binding environment is similar to closed environments proposed by J. Conery. However, unlike Conery's scheme, it supports OR and independent AND parallelism on both types of machines. The term representation, the algorithms for unification and the join algorithms for parallel AND branches are presented in this paper. We also detail the differences between our scheme and Conery's scheme. A compiler based on this binding environment has been implemented on a platform for machine independent parallel programming called the Chare Kernel     

A join algorithm for combining AND parallel solutions in AND/OR parallel systems

When two or more literals in the body of a Prolog clause are solved in (AND) parallel, their solutions need to bejoined to compute solutions for the clause. This is often a difficult problem in parallel Prolog systems that exploit OR and independent AND parallelism in Prolog programs. In several AND/OR parallel systems proposed recently, this problem is side-stepped at the cost of unexploited OR parallelism in the program, in part due to the complexity of the backtracking algorithm beneath AND parallel branches. In some cases, the data dependency graphs used by these systems cannot represent all the exploitable indenpendent AND parallelism known at compile time.In this paper, we describe the compile time analysis for an optimizedjoin algorithm for supporting independent AND parallelism in logic programs efficiently without leaving any OR parallelism unexploited. We then discuss how this analysis can be used to yield very efficient runtime behavior. We also discuss problems associated with a tree representation of the search space when arbitrarily complex data dependency graphs are permitted. We describe how these problems can be resolved by mapping the search space onto the data dependency graphs themselves. The algorithm has been implemented in a compiler for parallel Prolog based on the Reduce-OR process model. The algorithm is suitable for the implementation of AND/OR systems on both shared and nonshared memory machines. Performance on benchmark programs exhibiting AND and OR parallelism on one shared memory machine and one message passing machine is presented.This work was supported in part by NSF Grants CCR-87-00988 and CCR-89-02496.A shorter version of this paper appears in theProceedings of NACLP 1990.     

ACS算法在矩形件优化排料中的应用

矩形件优化排料是一类具有NP完全难度的组合优化问题。有关的优化问题可用与或树来描述,这样就把矩形件优化排料问题变换为寻找一棵面积比率最大的二叉树。用ACS算法实现这种树搜索,是把一定数量的人工蚂蚁分布在与或树的根节点,人工蚂蚁间通过使用信息素相互交流,完成从与或树到二叉树的选择,从而得到矩形件优化排料问题的优化解。     

Deterministic bit-stream digital neurons

In this paper, we present the design of a deterministic bit-stream neuron, which makes use of the memory rich architecture of fine-grained field-programmable gate arrays (FPGAs). It is shown that deterministic bit streams provide the same accuracy as much longer stochastic bit streams. As these bit streams are processed serially, this allows neurons to be implemented that are much faster than those that utilize stochastic logic. Furthermore, due to the memory rich architecture of fine-grained FPGAs, these neurons still require only a small amount of logic to implement. The design presented here has been implemented on a Virtex FPGA, which allows a very regular layout facilitating efficient usage of space. This allows for the construction of neural networks large enough to solve complex tasks at a speed comparable to that provided by commercially available neural-network hardware.     

Hyper-Distributed Hyper-Parallel Implementation of Heuristic Search of Implicit AND/OR Graph

This paper presents the hierarchic chaotic cellular networks for the hardware implementation of hyper-distributed hyper-parallel intelligent problem solving based on competitive wave propagation.By using the bifurcation and the synchronization of distributed chaotic dynamic systems,and by improving the Chua‘s circuit,the mechanism and the algorithms of heuristic search of an implicit AND/OR graph are realized in a hyper-distributed hyper-parallel environment.This paper‘s approach has many advantages in comparison with other traditional systolic structures based on symbolic logic algorithms.     

A reconfigurable architecture for autonomous visual-navigation

Abstract. This paper describes the design of a reconfigurable architecture for implementing image processing algorithms. This architecture is a pipeline of small identical processing elements that contain a programmable logic device (FPGA) and double port memories. This processing system has been adapted to accelerate the computation of differential algorithms. The log-polar vision selectively reduces the amount of data to be processed and simplifies several vision algorithms, making possible their implementation using few hardware resources. The reconfigurable architecture design has been devoted to implementation, and has been employed in an autonomous platform, which has power consumption, size and weight restrictions. Two different vision algorithms have been implemented in the reconfigurable pipeline, for which some experimental results are shown. Received: 30 March 2001 / Accepted: 11 February 2002 RID="*" ID="*" This work has been supported by the Ministerio de Ciencia y Tecnología and FEDER under project TIC2001-3546 Correspondence to: J.A. Boluda     

在操作系统中实现分布共享存储、存储管理和文件系统的集成

开发分布共享存储系统的目的是为了在分布式存储器的基础上构造逻辑上的共享存储器模型,对于如何在共享存储器模型的基础上为用户进程构造虚拟空间,传统的分布共享系统并未给予足够的重视。只有在操作系统中把分布共享存储技术、存储器管理和文件系统结合起来,才能充分发挥分布共享存储技术具有的能力。基于以上思想,在文中提出了一个实现了分布共享存储的操作系统模型,并分析了该模型一个实现原型,讨论该原型具有的优缺点。通过在操作系统中取消进程的逻辑空间,使进程直接在文件上运行,该模型不仅能够实现分布共享存储,而且和许多传统操作系统以及传统分布共享存储系统相比,具有许多优点。该操作系统实现了分布共享存储技术和操作系统中的存储管理以及文件系统的完美结合。     

Generalized Query-By-Rule: a heterogeneous database query language

This paper describes the design and implementation of a high-level query language called Generalized Query-By-Rule (GQBR) which supports retrieval, insertion, deletion and update operations. This language, based on the formalism of database logic, enables the users to access each database in a distributed heterogeneous environment, without having to learn all the different data manipulation languages. The compiler has been implemented on a DEC 1090 system in Pascal.     

Data management scheme for parallel radiosity

The radiosity method is a very demanding process in terms of computing and memory resources. To cope with these problems, parallel solutions have been proposed in the literature. A new parallel solution, based on the use of a shared virtual memory, is proposed. It will be shown that this concept of SVM greatly simplifies the implementation of a parallel algorithm since distributed data are managed by the operating system. This new parallel radiosity algorithm has been implemented on an iPSC/2 hypercube using the SVM. The first results obtained with this algorithm are encouraging since the calculated efficiency curve is nearly linear.     

The pervasiveness of evolution in GRUMPS software

This paper describes the evolution of the design and implementation of a distributed run‐time system that itself is designed to support the evolution of the topology and implementation of an executing, distributed system. The three different versions of the run‐time architecture that have been designed and implemented are presented, together with how each architecture addresses the problems of topological and functional evolution. In addition, the reasons for the rapid evolution of the design and implementation of the architecture are also described. From the lessons learned in both evolving the design of the architecture and in trying to provide a run‐time system that can support run‐time evolution, this paper discusses two generally applicable observations: evolution happens all the time, and it is not possible to anticipate how systems will evolve as designs; and large, run‐time systems do not follow a predictable path. In addition to this, rapid prototyping has proved to be extremely useful in the production of the three architectures; this kind of prototyping has been made much easier by designing the core set of Java abstractions in terms of interfaces; and building an architecture that allows as many decisions as possible to be made at run‐time which has produced a support system that is more responsive to the user as well as the distributed environment in which it is executing. Copyright © 2003 John Wiley & Sons, Ltd.     

分布仿真系统中MVC控制器的研究与设计

该文基于14LA／RTI环境下分布仿真系统的实现方法,使用MVC设计模式分析现有分布仿真系统框架,提出一种新的构架分布仿真系统的方法。使用这种方法,可以实现应用逻辑与事务逻辑的分离;可以根据规范独立完成实体模型和表现部分的建模,形成丰富的资源库,通过控制器完成系统的集成。控制器作为框架中相对稳定的部件,具有高度可重用性。该文的重点落于控制器的设计,使用XML描述数据交换规范。     

Distributed logic objects

This paper presents a language based on the logic programming paradigm that supports objects, messages and inheritance. The object-oriented extension is fairly simple: objects are clusters of processes, objects' state is represented by logical variables, message-passing communication between objects is performed via multi-head clauses, and inheritance is mapped into clause union. The language implementation is obtained by translating logic objects into a concurrent logic language based on multi-head clauses, taking advantage of its distributed implementation on a massively parallel architecture. The runtime support realizes some interesting features such as intensional messages and the transparency of object allocation, object migration and parallelism.     

元数据驱动的数据采集系统的设计

对数据采集、元数据的概念及元数据驱动的数据采集系统的设计原则和实现方案进行了探讨.提出了通过分离系统中的元数据来实现将采集逻辑和业务逻辑相分离的数据采集体系架构.实践表明,该方案在数据仓库、数据中心等决策系统中的应用,可有效提高系统的灵活性和扩展性.     

Static analysis of a parallel logic language based on the blackboard model

Shared Prolog is a parallel logic language based on the blackboard interpretation of logic programming. In such an interpretation a logic program is seen as a set of rules executed by a set of agents cooperating via a shared working memory called the blackboard. A distributed interpreter for Shared Prolog was implemented and described in another paper, where the blackboard was a centralized data structure. In this paper we show how the blackboard can be distributed using some static analysis techniques. The basic idea is to perform an abstract interpretation starting from the Shared Prolog operational semantics to generate data structures which represent possible interactions and links among agents. The resulting data structures are used to reduce the number of run time communication operations in an implementation distributed over a network of workstations.     

AND parallelism and nondeterminism in logic programs

This paper defines an abstract interpreter for logic programs based on a system of asynchronous, independent processors which communicate only by passing messages. Each logic program is automatically partitioned and its pieces distributed to available processors. This approach permits two distinct forms of parallelism. OR parallelism arises from evaluating nondeterministic choices simultaneously. AND parallelism arises when a computation involves independent, but necessary, subcomputations. Algorithms like quicksort, which follow a divide and conquer approach, usually exhibit this form of parallelism. These two forms of parallelism are conjointly achieved by the parallel interpreter.