Parallel stereocorrelation on a reconfigurable multi-ring network

A reconfigurable network termed as the reconfigurable multi-ring network (RMRN) is described. The RMRN is shown to be a truly scalable network in that each node in the network has a fixed degree of connectivity and the reconfiguration mechanism ensures a network diameter of O(log₂ N) for anN-processor network. Algorithms for the two-dimensional mesh and the SIMD or SPMD n-cube are shown to map very elegantly onto the RMRN. Basic message passing and reconfiguration primitives for the SIMD/SPMD RMRN are designed for use as building blocks for more complex parallel algorithms. The RMRN is shown to be a viable architecture for image processing and computer vision problems using the parallel computation of the stereocorrelation imaging operation as an example. Stereocorrelation is one of the most computationally intensive imaging tasks. It is used as a visualization tool in many applications, including remote sensing, geographic information systems and robot vision.An earlier version of this paper was presented at the 1995 International Conference on Parallel and Distributed Processing Techniques and Applications.     

Accuracy-Based Sampling and Reconstruction with Adaptive Meshes for Parallel Hierarchical Triangulation

Recent advances in range finding techniques have made the task of acquiring surface data for 3-D objects easier and more accurate. With most advanced techniques, range and color data are acquired simultaneously. Since the number of such acquired data is generally very large, a surface model capable of compressing data while maintaining a specified accuracy is required. The objective of this work is to construct a polyhedral representation of input data for surfaces. This representation adapts to local intrinsic surface properties while preserving their discontinuities. In this paper, we present an accuracy-based adaptive sampling and reconstruction technique for hierarchical triangulation of 3D objects. We have developed a parallel algorithm for adaptive mesh generation that recursively bisects mesh elements by increasing the number of mesh nodes according to local surface properties, such as surface orientation, curvature, and color. The recursive subdivision based on such viewpoint-invariant properties yields a hierarchical surface triangulation that is intrinsic to the surface. This approach also satisfies the absolute accuracy criteria, since nodes are generated as required until the entire surface has been approximated within a specified level of accuracy. We have also developed a parallel algorithm that detects and preserves both depth (C⁰) and orientation (C¹) discontinuities, without the formation of cracks which normally occur during independent subdivision. The algorithm has been successfully applied to adaptive sampling and reconstruction of both range and color images of human faces and Japanese antique dolls with fine grained color-texture.     

基于多变体的控制软件异构冗余与动态重构技术研究

针对控制软件的防篡改问题,从工控安全角度出发,提出了一种利用多变体技术和虚拟化技术构建控制软件动态目标防御体系的新方法;通过多变体的异构冗余、动态重构和多模表决实现了软件层面的主动防御和安全态势感知,通过虚拟化技术实现了多变体执行环境的快速构建;着重介绍了技术路线、系统架构、动态重构策略、表决算法和同步机制;研究结果表明,该技术在提高控制系统可靠性的同时,使其具备了较强的主动安全防御能力。     

Comparative analysis of two different middleware approaches for reconfiguration of distributed real-time systems

Software-based reconfiguration of distributed real-time systems is a complex problem with many sides to it ranging from system-wide concerns down to the intrinsic non-robust nature of the specific middleware layer and the used programming techniques. In a completely open distributed system, mixing reconfiguration and real-time is not possible; the set of possible target states can be very large threatening the temporal predictability of the reconfiguration process. Over the last years, middle ware solutions have appeared mainly for general purpose systems where efficient state transitions are sought for, but real-time properties are not considered. One of the few contributions to run-time software reconfiguration in distributed real-time environments has been the iLAND middleware, where the germ of a solution with high potential has been conceived and delivered in practice.¹ The key idea has been the fact that a set of bounds and limitations to the structure of systems and to their open nature needs to be imposed in order to come up with practical solutions. In this paper, the authors present the different sides of the problem of software reconfiguration from two complementary middleware perspectives comparing two strategies built inside distribution middleware. We highlight the lessons learned in the iLAND project aimed at service-based reconfiguration and compare it to our experience in the development of distributed real-time Java reconfiguration based on distributed tasks rescheduling. Authors also provide a language view of both solutions. Lastly, empirical results are shown that validate these solutions and compare them on the basis of different programming language realizations.     

Intel virtualization technology

A virtualized system includes a new layer of software, the virtual machine monitor. The VMM's principal role is to arbitrate accesses to the underlying physical host platform's resources so that multiple operating systems (which are guests of the VMM) can share them. The VMM presents to each guest OS a set of virtual platform interfaces that constitute a virtual machine (VM). Once confined to specialized, proprietary, high-end server and mainframe systems, virtualization is now becoming more broadly available and is supported in off-the-shelf systems based on Intel architecture (IA) hardware. This development is due in part to the steady performance improvements of IA-based systems, which mitigates traditional virtualization performance overheads. Intel virtualization technology provides hardware support for processor virtualization, enabling simplifications of virtual machine monitor software. Resulting VMMs can support a wider range of legacy and future operating systems while maintaining high performance.     

Fault‐tolerant adaptive control allocation schemes for overactuated systems

This paper presents a fault‐tolerant adaptive control allocation scheme for overactuated systems subject to loss of effectiveness actuator faults. The main idea is to use an ‘ad hoc’ online parameters estimator, coupled with a control allocation algorithm, in order to perform online control reconfiguration whenever necessary. Time‐windowed and recursive versions of the algorithm are proposed for nonlinear discrete‐time systems and their properties analyzed. Two final examples have been considered to show the effectiveness of the proposed scheme. The first considers a simple linear system with redundant actuators and it is mainly used to exemplify the main properties and potentialities of the scheme. In the second, a realistic marine vessel scenario under propeller and thruster faults is treated in full details. Copyright © 2010 John Wiley & Sons, Ltd.     

Network-on-Chip virtualization in Chip-Multiprocessor Systems

It is expected that Chip Multiprocessor Systems (CMPs) will contain more and more cores in every new generation. However, applications for these systems do not scale at the same pace. In order to obtain a good CMP utilization several applications will need to coexist in the system and in those cases virtualization of the CMP system will become mandatory. In this paper we analyze two virtualization strategies at NoC-level aiming to isolate the traffic generated by each application to reduce or even eliminate interferences among messages belonging to different applications. The first model handles most interferences among messages with a virtual-channels (VCs) implementation reducing both execution time and network latency. However, using VCs results in area and power overhead due to the cost of control and buffer implementation. In contrast, the second model is based on the resource partitioning strategies which results in a space partitioning of the CMP chip in several regions. For this last model, Virtual-Regions (VR), we use a reconfiguration algorithm of the network that is able to dynamically adapt the network partitions in order to satisfy the application requirements. The paper shows a comparison of both models and identifies their main advantages and disadvantages. From our experimental results, we show that our proposal obtains in terms of execution time average improvements of 30% for parallel applications when compared to a baseline scenario. Moreover, when compared to a VCs implementation, our proposal improves the average execution time by 9% for parallel applications.     

嵌入式虚拟化技术

计算机系统虚拟化技术是IT领域近几年的热点技术。虚拟化技术的下一步发展方向是嵌入式系统。嵌入式系统进行虚拟化是在嵌入式硬件平台和操作系统之间加入一层叫做虚拟机管理器的软件,由后者构造出可运行多种操作系统的虚拟机。国外多家公司和大学已对嵌入式虚拟化技术展开研究。嵌入式虚拟化的好处包括减少嵌入式系统开发成本、缩短产品上市周期、利于整合功能、减少功耗、软件资产保值和增强安全性与可靠性。嵌入式虚拟化技术面临的问题包括实时调度问题、嵌入式硬件平台多样性问题、电源管理问题以及跨虚拟机通信问题。嵌入式虚拟化技术将给嵌入式领域带来重大变化,值得关注。     

Enabling OpenCL support for GPGPU in Kernel‐based Virtual Machine

The importance of heterogeneous multicore programming is increasing, and Open Computing Language (OpenCL) is an open industrial standard for parallel programming that provides a uniform programming model for programmers to write efficient, portable code for heterogeneous computing devices. However, OpenCL is not supported in the system virtualization environments that are often used to improve resource utilization. In this paper, we propose an OpenCL virtualization framework based on Kernel‐based Virtual Machine with API remoting to enable multiplexing of multiple guest virtual machines (guest VMs) over the underlying OpenCL resources. The framework comprises three major components: (i) an OpenCL library implementation in guest VMs for packing/unpacking OpenCL requests/responses; (ii) a virtual device, called virtio‐CL, that is responsible for the communication between guest VMs and the hypervisor (also called the VM monitor); and (iii) a thread, called CL thread, that is used for the OpenCL API invocation. Although the overhead of the proposed virtualization framework is directly affected by the amount of data to be transferred between the OpenCL host and devices because of the primitive nature of API remoting, experiments demonstrated that our virtualization framework has a small virtualization overhead (mean of 6.8%) for six common device‐intensive OpenCL programs and performs well when the number of guest VMs involved in the system increases. These results indirectly infer that the framework allows for effective resource utilization of OpenCL devices.Copyright © 2012 John Wiley & Sons, Ltd.     

Intermediate-level feature extraction in novel parallel environments

Abstract. Parallel systems provide an approach to robust computing. The motivation for this work arises from using modern parallel environments in intermediate-level feature extraction. This study presents parallel algorithms for the Hough transform (HT) and the randomized Hough transform (RHT). The algorithms are analyzed in two parallel environments: multiprocessor computers and workstation networks. The results suggest that both environments are suitable for the parallelization of HT. Because scalability of the parallel RHT is weaker than with HT, only the multiprocessor environment is suitable. The limited scalability forces us to use adaptive techniques to obtain good results regardless of the number of processors. Despite the fact that the speedups with HT are greater than with RHT, in terms of total computation time, the new parallel RHT algorithm outperforms the parallel HT. Received: 8 December 2001 / Accepted: 5 June 2002 Correspondence to: V. Kyrki     

A Fast Algorithm for k-Nearest Neighbor Problem on a Reconfigurable Mesh Computer

Given a set S of m points stored on a reconfigurable mesh computer of size n×n, one point per processing element (PE). In this paper we present a parallel method for solving the k-Nearest Neighbor problem (k-NN). This method permits each point of S to know its k-NN (0<k<m). The corresponding algorithm requires that each PE must have 2k registers where it stores the (x,y) coordinates of its k-NN in a given order. This algorithm has a complexity of O(logh+k ²) times, where h is a maximal number of points within a row of the mesh. This complexity is reduced to O(k ²) times, using an appropriate procedure which demonstrates the power of the reconfiguration operations carried out by the processors, and the polymorphic properties of the mesh.     

Multi-Camera Active-Vision for Markerless Shape Recovery of Unknown Deforming Objects

A novel multi-camera active-vision reconfiguration method is proposed for the markerless shape recovery of unknown deforming objects. The proposed method implements a model fusion technique to obtain a complete 3D mesh-model via triangulation and a visual hull. The model is tracked using an adaptive particle filtering algorithm, yielding a deformation estimate that can, then, be used to reconfigure the cameras for improved surface visibility. The objective of reconfiguration is maximization of the total surface area visible through stereo triangulation. The surface area based objective function directly relates to maximizing the accuracy of the shape recovered, as stereo triangulation is more accurate than visual hull building when the number of viewpoints is limited. The reconfiguration process comprises workspace discretization, visibility estimation, optimal stereo-pose selection, and path planning to ensure 2D tracked feature consistency. In contrast to other reconfiguration techniques that rely on a priori known, and at times static, object models, our method focuses on a priori unknown deforming objects. The proposed method operates on-line and has been shown to outperform static-camera based systems through extensive simulations and experiments with an increased surface visibility in the presence of occluding obstacles.     

vMES: Virtualization aware manufacturing execution system

The large scale emergence in the last decade of various cloud solutions, ranging from software-as-a-service (SaaS) based solutions for business process management and implementation to very sophisticated private cloud solutions capable of high performance computing (HPC) and efficient virtualization, constitute the building blocks for engineering the next generation of flexible enterprise systems that can respond with great agility to changes in their environment. These new technologies are adopted at a certain level by manufacturing enterprises in order to advance in a new era of mass customization where flexibility, scalability and agility are the differentiating factors. In this context, this paper introduces the virtualized manufacturing execution system (vMES), an intermediate layer in the manufacturing stack, and discusses the advantages and limitations offered by this approach for manufacturing enterprises. A classification of MES workloads based on the ISA-95 function model is presented, focusing on the virtualization techniques suitable for each workload, considering the algorithms and technologies used and the virtualization overhead. A pilot vMES implementation using a parallel process for smart resource provisioning and automatic scaling is also presented. The pilot implementation using six Adept robots and one IBM CloudBurst 2.1 private cloud and an ISA-95 based MES is described; the virtualization sequence is analyzed in several scenarios of resource workload collocation on physical cloud blades with and without perturbations.     

Parallel reconfiguration algorithms for mesh-connected processor arrays

Effective fault tolerance techniques are essential for improving the reliability of multiprocessor systems. At the same time, fault tolerance must be achieved at high speed to meet the real-time constraints of embedded systems. While parallelism has often been exploited to increase performance, to the best of our knowledge, there has been no previously reported work on parallel reconfiguration of mesh-connected processor arrays with faults. This paper presents two parallel algorithms to accelerate reconfiguration of the processor arrays. The first algorithm reconfigures a host array in parallel in a multithreading manner. The threads in the parallel algorithm execute independently within a safe rerouting distance. The second algorithm is based on a divide-and-conquer approach to first generate the leftmost segments in parallel and then merge the segments in parallel. When compared to the conventional algorithm, simulation results from a large number of instances confirm that the proposed algorithms significantly accelerate the reconfiguration without loss of harvest.     

Zorilla: a peer‐to‐peer middleware for real‐world distributed systems

The inherent complex nature of current distributed computing architectures hinders the widespread adoption of these systems for mainstream use. In general, users have access to a highly heterogeneous set of compute resources, which may include clusters, grids, desktop grids, clouds, and other compute platforms. This heterogeneity is especially problematic when running parallel and distributed applications. Software is needed which easily combines as many resources as possible into one coherent computing platform. In this paper, we introduce Zorilla: peer‐to‐peer (P2P) middleware that creates a single distributed environment from any available set of compute resources. Zorilla imposes minimal requirements on the resource used, is platform independent, and does not rely on central components. In addition to providing functionality on bare resources, Zorilla can exploit locally available middleware. Zorilla explicitly supports distributed and parallel applications, and allows resources from multiple sites to cooperate in a single computation. Zorilla makes extensive use of both virtualization and P2P techniques. We will demonstrate how virtualization and P2P combine into a simple design, while enhancing functionality and ease of use. Together, these techniques bring our goal a step closer: transparent, easy use of resources, even on very heterogeneous distributed systems. Copyright © 2011 John Wiley & Sons, Ltd.     

一种基于集群环境的虚拟存储系统研究与实现

虚拟存储管理系统能够根据用户的需要随时在线调整存储卷的容量，而且能够提供快照、在线数据备份等功能，成为存储系统中重要的功能中间件．然而传统的服务器存储管理系统不能适应集群环境下的数据管理，尤其是随着SANs（Storage Area Networks）技术的日益发展与普及，研究集群环境下的虚拟存储系统成为迫切任务．本文通过对虚拟存储技术的研究，提出了集群环境下虚拟存储系统的模型CVM．分析了其中的关键技术．并且给出了一个具体的实现方案和测试结果，结果表明，CVM系统能够有效实现共享存储环境下的虚拟存储管理．同时提供了在线数据备份、数据镜像等功能，具有很好的容错特性，较好实现了集群环境下的共享存储管理．     

Prospects for virtualization of high-performance x64 systems

Prospects for applying virtualization technology in high-performance computations on the x64 systems are studied. Principal reasons for performance degradation when parallel programs are running in virtual environments are considered. The KVM/QEMU and Palacios virtualization systems are considered in detail, with the HPC Challenge and NAS Parallel Benchmarks used as benchmarks. A modern computing cluster built on the Infiniband high-speed interconnect is used in testing. The results of the study show that, in general, virtualization is reasonable for a wide class of high-performance applications. Fine tuning of the virtualization systems involved made it possible to reduce overheads from 10–60% to 1–5% on the majority of tests from the HPC Challenge and NAS Parallel Benchmarks suites. The main bottlenecks of virtualization systems are reduced performance of the memory system (which is critical only for a narrow class of problems), costs associated with hardware virtualization, and the increased noise caused by the host operating system and hypervisor. Noise can have a negative effect on performance and scalability of fine-grained applications (applications with frequent small-scale communications). The influence of noise significantly increases as the number of nodes in the system grows.     

Fast parallel solution of boundary integral equations and related problems

This article is concerned with the efficient numerical solution of Fredholm integral equations on a parallel computer with shared or distributed memory. Parallel algorithms for both, the approximation of the discrete operator by hierarchical matrices using adaptive cross approximation (ACA) and the parallel matrix-vector multiplication of such matrices by a vector, are presented. The first algorithm has a complexity of order p ^-1 N log^2d-1 N, while the latter is of order p ^-1 N log ^d N, where N, d and p are the number of unknowns, the spatial dimension and the number of processors, respectively. The approximant needs Ω(p ^-1 N log ^d N) units of storage on each processor. Dedicated to George C. Hsiao on the occasion of his 70th birthday. Mathematics Subject Classification (2000)65D05 65D15 65F05 65F30 Communicated by: U. Langer     

Dynamic power optimization by exploiting self-reconfiguration in Xilinx Spartan 3-based systems

Reconfigurable architectures are increasingly often applied in various industrial data processing applications, due to the possibility for performing parallel computations and achieving a simplified Systemon-Chip design flow. Furthermore, the exploitation of dynamic and partial hardware reconfiguration has been investigated in different research projects, often in systems based on Xilinx Virtex 2/4 FPGA families, by time-multiplexing hardware resources for multiple functions. This paper describes the exploitation of partial reconfiguration for dynamic power management in a low-power Spartan 3-based level measurement application. The reconfiguration process is thereby applied to optimize system implementation according to the applications requirements on power consumption and performance.