A holistic approach for tightly coupled reconfigurable parallel processors

New standards in signal, multimedia, and network processing for embedded electronics are characterized by computationally intensive algorithms, high flexibility due to the swift change in specifications. In order to meet demanding challenges of increasing computational requirements and stringent constraints on area and power consumption in fields of embedded engineering, there is a gradual trend towards coarse-grained parallel embedded processors. Furthermore, such processors are enabled with dynamic reconfiguration features for supporting time- and space-multiplexed execution of the algorithms. However, the formidable problem in efficient mapping of applications (mostly loop algorithms) onto such architectures has been a hindrance in their mass acceptance. In this paper we present (a) a highly parameterizable, tightly coupled, and reconfigurable parallel processor architecture together with the corresponding power breakdown and reconfiguration time analysis of a case study application, (b) a retargetable methodology for mapping of loop algorithms, (c) a co-design framework for modeling, simulation, and programming of such architectures, and (d) loosely coupled communication with host processor.     

Partitioning and mapping in embedded multiprocessor architectures in the presence of constraints

The paper focuses on the problem of partitioning and mapping parallel programs onto heterogeneous embedded multiprocessor architectures for real-time applications. Such applications present unique constraints and challenges. In addition to heterogeneity, the proposed partitioning and mapping algorithms satisfy memory, task throughput, task placement, intertask communication bandwidth, and co-location constraints. They do so for architectures that utilize circuit-switched (rather than packet-switched) interprocessor communication and optimize latency and throughput in addition to load-balancing. Finally, these mapping algorithms make use of knowledge of the local scheduling discipline to accommodate real-time scheduling constraints. Our focus is on unstructured parallel programs that fall into one of two classes: (i) the class of computations characteristic of control applications in a real-time environment where tasks execute concurrently, periodically exchanging information, and (ii) pipelined computation graphs found in sensor data processing applications. The algorithms are implemented in a set of tools that operate with commercial CASE tools at one end, and present an interface to multiprocessor simulators at the other end. Collectively, the algorithms form a significant component of an interactive design environment for the development and mapping of real-time embedded parallel programs. The paper describes the algorithms, the encapsulating toolset, and presents an example of their application to an existing embedded application—an Autonomous Underwater Vehicle application.     

Global Optimization for Mapping Parallel Image Processing Tasks on Distributed Memory Machines

Many parallel algorithms and library routines for computer vision and image processing (CVIP) tasks on distributed-memory multiprocessors are available. The typical image distribution may use column, row, and block based mapping. Integrating a set of library routines for a CVIP application requires a global optimization to determine the data mapping of individual tasks by considering inter-task communication. The main difficulty in deriving the optimal image data distribution for each task is that CVIP task computation may involve loops, and the number of processors available and the size of the input image may vary at the run time. In this paper, a CVIP application is modeled using a task chain with imperfectly nested loops, specified by conventional visual languages such asKhorosandExplorer. A mapping algorithm is proposed that optimizes the average run-time performance for CVIP applications with nested loops by considering the data redistribution overheads and possible run-time parameter variations. A taxonomy of CVIP operations is provided and used for further reducing the complexity of the algorithm. Experimental results on both low-level image processing and high-level computer vision applications are presented to validate this approach.     

Joint application mapping/interconnect synthesis techniques for embedded chip-scale multiprocessors

As transistor sizes shrink, interconnects represent an increasing bottleneck for chip designers. Several groups are developing new interconnection methods and system architectures to cope with this trend. New architectures require new methods for high-level application mapping and hardware/software codesign. We present high-level scheduling and interconnect topology synthesis techniques for embedded multiprocessor systems-on-chip that are streamlined for one or more digital signal processing applications. That is, we seek to synthesize an application-specific interconnect topology. We show that flexible interconnect topologies utilizing low-hop communication between processors offer advantages for reduced power and latency. We show that existing multiprocessor scheduling algorithms can deadlock if the topology graph is not strongly connected, or if a constraint is imposed on the maximum number of hops allowed for communication. We detail an efficient algorithm that can be used in conjunction with existing scheduling algorithms for avoiding this deadlock. We show that it is advantageous to perform application scheduling and interconnect synthesis jointly, and present a probabilistic scheduling/interconnect algorithm that utilizes graph isomorphism to pare the design space.     

Integrated core selection and mapping for mesh based Network-on-Chip design with irregular core sizes

Network-on-Chip (NoC) has been proposed to replace traditional bus based System-on-Chip (SoC) architecture to address the global communication challenges in nanoscale technologies. A major challenge in NoC based system design is to select Intellectual Property (IP) cores for implementing tasks and associate the selected cores to the routers to optimize cost and performance. These are commonly known as the process of core selection and application mapping respectively. In this paper, integrated core selection and mapping problem has been addressed. Mesh architecture has been considered for experimentation. The integrated core selection and mapping problem takes as input the application task graph, topology graph and a core library. It outputs the selected cores for the tasks and their mapping onto the topology graph, such that, all communication requirements of the application are satisfied. The cores present in a core library may perform more than one task and have non-uniform sizes. For this, a technique based on Particle Swarm Optimization (PSO) has been proposed to select cores from the given core library and map the resultant core graph onto mesh based architectures. An efficient heuristic for mapping has also been proposed, which maps the selected cores onto mesh based architectures, considering non-uniform core sizes. Comparisons have been carried out with step-by-step core selection and mapping approach and also with mapping algorithms that exist in the literature. Significant reductions have been observed in terms of communication cost over all the cases. Area comparisons have also been made. On average, improvement of 13.05% in communication cost and 2.07% in area have been observed. The proposed approach has also been compared in dynamic environment and significant reductions in the average network latency could be observed. On average, improvement of 5.48% in average network latency and 15.68% in network throughput has been observed. Comparison of energy consumption has also been done in both the cases.     

Optimal Use of Mixed Task and Data Parallelism for Pipelined Computations

This paper addresses optimal mapping of parallel programs composed of a chain of data parallel tasks onto the processors of a parallel system. The input to the programs is a stream of data sets, each of which is processed in order by the chain of tasks. This computation structure, also referred to as a data parallel pipeline, is common in several application domains, including digital signal processing, image processing, and computer vision. The parameters of the performance for such stream processing are latency (the time to process an individual data set) and throughput (the aggregate rate at which data sets are processed). These two criteria are distinct since multiple data sets can be pipelined or processed in parallel. The central contribution of this research is a new algorithm to determine a processor mapping for a chain of tasks that optimizes latency in the presence of a throughput constraint. We also discuss how this algorithm can be applied to solve the converse problem of optimizing throughput with a latency constraint. The problem formulation uses a general and realistic model of intertask communication and addresses the entire problem of mapping, which includes clustering tasks into modules, assigning of processors to modules, and possible replicating of modules. The main algorithms are based on dynamic programming and their execution time complexity is polynomial in the number of processors and tasks. The entire framework is implemented as an automatic mapping tool in the Fx parallelizing compiler for a dialect of High Performance Fortran.     

TT-BIP: using correct-by-design BIP approach for modelling real-time system with time-triggered paradigm

In order to combine advantages of real-time operating systems implementing the time-triggered (TT) execution model and model-based design frameworks, we aim at proposing a correct-by-design methodology that derives correct TT implementations from high-level models. This methodology consists of two main steps: (1) transforming the high-level model into an intermediate model which respects the TT communication principles and where all communications between components are simple send/receive interactions, and (2) transforming the obtained intermediate model into the programming language of the target platform. In this paper, we focus on the presentation of the transformational methodology of the first step of this design flow. This methodology produces a correct-by-construction TT model by starting from a high-level model of the application software in behaviour, interaction, priority (BIP). BIP is a component-based framework with formal semantics that rely on multiparty interactions for synchronizing components. Commonly in TT implementations, tasks interact with each other through a communication medium. Our methodology transforms, depending on a user-defined task mapping, high-level BIP models where communication between components is strongly synchronized, into TT model that integrates a communication medium. Thus, only inter-task communications and components participating in such interactions are concerned by the transformation process. We also provide correctness proofs of the transformation and apply it on an industrial case study.     

拓扑结构感知的片上网络体系结构应用映射与优化

应用映射是片上网络体系结构研究的关键问题之一,映射结果的好坏会极大地影响体系结构的性能。现有的应用映射方法大多基于特定的网络结构,如2d-mesh、2d-torus等,研究NoC性能或功耗约束的应用映射与优化方法。本文提出了一种拓扑结构感知的基于高层代码转换的片上网络应用映射与优化方法。该方法采用多面体模型对应用的核心循环进行自动并行和局部性优化,并将网络拓扑结构抽象成带权重的有向图,使用该有向图对任务流图进行覆盖,以提高任务的并行性,降低任务间同步和通信开销。实验结果表明,采用优化的映射方法后任务节点间的并行性被充分利用,通信开销降低,整体上提高了片上网络系统性能。     

pp-mess-sim: a flexible and extensible simulator for evaluatingmulticomputer networks

The paper presents pp-mess-sim, an object-oriented discrete-event simulation environment for evaluating interconnection networks in message-passing systems. The simulator provides a toolbox of various network topologies, communication workloads, routing-switching algorithms, and router models. By carefully defining the boundaries between these modules, pp-mess-sim creates a flexible and extensible environment for evaluating different aspects of network design. The simulator models emerging multicomputer networks that can support multiple routing and switching schemes simultaneously; pp-mess-sim achieves this flexibility by associating routing-switching policies, traffic patterns, and performance metrics with collections of packets, instead of the underlying router model. Besides providing a general framework for evaluating router architectures, pp-mess-sim includes a cycle-level model of the PRC, a programmable router for point-to-point distributed systems. The PRC model captures low-level implementation details, while another high-level model facilitates experimentation with general router design issues. Sample simulation experiments capitalize on this flexibility to compare network architectures under various application workloads     

Domain-Specific Modeling for Rapid Energy Estimation of Reconfigurable Architectures

Reconfigurable architectures such as FPGAs are flexible alternatives to DSPs or ASICs used in mobile devices for which energy is a key performance metric. Reconfigurable architectures offer several design parameters such as operating frequency, precision, amount of memory, degree of parallelism, etc. These parameters define a large design space that must be explored to find energy-efficient solutions. It is also challenging to predict the energy variation at the early design phases when a design is modified at algorithm level. Efficient traversal of such a large design space requires high-level modeling to facilitate rapid estimation of system-wide energy. However, FPGAs do not exhibit a high-level structure like, for example, a RISC processor for which high-level as well as low-level energy models are available. To address this scenario, we propose a domain-specific modeling technique for energy-efficient kernel design that exploits the knowledge of the algorithm and the target architecture family for a given kernel to develop a high-level model. This model captures architecture and algorithm features, parameters affecting energy performance, and power estimation functions based on these parameters. A system-wide energy function is derived based on the power functions and cycle specific power state of each building block of the architecture. This model is used to understand the impact of various parameters on system-wide energy and can be a basis for the design of energy-efficient algorithms. Our high-level model is used to quickly obtain fairly accurate estimate of the system-wide energy dissipation of data paths configured using FPGAs. We demonstrate our modeling methodology by applying it to four domains.     

Parallel computation of symbolic robot models and control laws: Theory and application to transputer networks

New computer architectures based on large numbers of processors are now used in various application areas ranging from embedded systems to supercomputers. Efficient parallel processing algorithms are applied in a wide variety of applications such as simulation, robot control, and image synthesis. This article presents two novel parallel algorithms for computing robot inverse dynamics (as well as control laws) starting from customized symbolic robot models. To gain the most benefit from the concurrent processor architecture, the whole job is divided into a large number of simple tasks, each involving only a single floating-point operation. Although requiring sophisticated scheduling schemes, fine granularity of tasks was the key factor for achieving nearly maximum efficiency and speedup. The first algorithm resolves the scheduling problem for an array of pipelined processors. The second one is devoted to parallel processors connected by a complete crossbar interconnection network. The main feature of the proposed algorithms is that they take into account the communication delays between processors and minimize both the execution time and communication cost. To prove the theoretical results, the algorithms have been verified by experiments on an INMOS T800 transputer-based system. We used four transputers in serial and parallel configurations. The experimental results show that the most complicated dynamic control laws can be executed in a submilisecond time interval. © 1993 John Wiley & Sons, Inc.     

Parallel Image Correlation: Case Study to Examine Trade-Offs in Algorithm-to-Machine Mappings

Performance of a parallel algorithm on a parallel machine depends not only on the time complexity of the algorithm, but also on how the underlying machine supports the fundamental operations used by the algorithm. This study analyzes various mappings of image correlation algorithms in SIMD, MIMD, and mixed-mode environments. Experiments were conducted on the Intel Paragon, MasPar MP-1, nCUBE 2, and PASM prototype. The machine features considered in this study include: modes of parallelism, communication/computation ratio, network topology and implementation, SIMD CU/PE overlap, and communication/computation overlap. Performance of an implementation can be enhanced by using algorithmic techniques that match the machine features. Some algorithmic techniques discussed here are additional communication versus redundant computation, data block transfers, and communication/computation overlap. The results presented are applicable to a large class of image processing tasks. Case studies, such as the one presented here, are a necessary step in developing software tools for mapping an application task onto a single parallel machine and for mapping the subtasks of an application task, or a set of independent application tasks, onto a heterogeneous suite of parallel machines.     

Scalable communication architectures for massively parallel hardware multi-processors

Modern complex embedded applications in multiple application fields impose stringent and continuously increasing functional and parametric demands. To adequately serve these applications, massively parallel multi-processor systems on a single chip (MPSoCs) are required. This paper is devoted to the design of scalable communication architectures of massively parallel hardware multi-processors for highly-demanding applications. We demonstrated that in the massively parallel hardware multi-processors the communication network influence on both the throughput and circuit area dominates the processors influence, while the traditionally used flat communication architectures do not scale well with the increase of parallelism. Therefore, we propose to design highly optimized application-specific partitioned hierarchical organizations of the communication architectures through exploiting the regularity and hierarchy of the actual information flows of a given application. We developed related communication architecture synthesis strategies and incorporated them into our quality-driven model-based multi-processor design methodology and related automated architecture exploration framework. Using this framework we performed a large series of architecture synthesis experiments. Some of the results of the experiments are presented in this paper. They demonstrate many features of the synthesized communication architectures and show that our method and related framework are able to efficiently synthesize well scalable communication architectures even for the high-end massively parallel multi-processors that have to satisfy extremely stringent computation demands.     

Local search to improve coordinate-based task mapping

We present a local search strategy to improve the coordinate-based mapping of a parallel job’s tasks to the MPI ranks of its parallel allocation in order to reduce network congestion and the job’s communication time. The goal is to reduce the number of network hops between communicating pairs of ranks. Our target is applications with a nearest-neighbor stencil communication pattern running on mesh systems with non-contiguous processor allocation, such as Cray XE and XK Systems. Using the miniGhost mini-app, which models the shock physics application CTH, we demonstrate that our strategy reduces application running time while also reducing the runtime variability. We further show that mapping quality can vary based on the selected allocation algorithm, even between allocation algorithms of similar apparent quality.     

A model-driven engineering framework for embedded systems design

This work presents a Model-Driven Engineering (MDE) framework to improve embedded system design. The framework adopts concepts from MDE for the automatic generation of a control and data flow internal representation, starting from the functional specification of an embedded application described using UML class and sequence diagrams. By means of transformations rules applied on the UML model of the embedded system, an MOF-based (Meta Object Facility is a standard representation for meta-models and models proposed by OMG) internal representation is automatically obtained, which is iteratively mapped into a hardware/software implementation by means of model transformations. This mapping is optimized by a design space exploration (DSE) method based on a categorical graph product. The model transformations have also as input a platform model, which specifies the available hardware, software and interface resources, and produce an implementation model, on which software synthesis, communication synthesis and high-level synthesis algorithms are applied to generate the final implementation. A case study is described to illustrate the application of the framework.     

Energy efficient heuristic application mapping for 2-D mesh-based network-on-chip

Application mapping in 2-D mesh-based Network-on-Chip (NoC) architecture is an optimization problem in which each application task (e.g., processor or memory units) should be mapped one-to-one onto a network element (switch or router) to optimize performance requirements (e.g., communication energy or communication latency) under certain platform constraints (e.g., bandwidth and/or latency). Network-on-Chip is a scheme that establishes links between limited application-specific components within Multi-Processor System-on-Chip (MPSoC), but it has a vital role to ensure the maximum data transfer rate and reduce total number of physical interconnections. Most of the works on heuristic application mapping for mesh-based NoC design aim to minimize both total communication energy and run-time, however they experience the following issues: (i) relatively high CPU time due to linear search for the task and tile mapping combinations, (ii) consumption of relatively high communication energy due to random tile selection when two or more tiles are equivalent in terms of average weighted distance by their adjacent mapped tasks, and (iii) even after constructive application mapping, some of the tasks consume higher communication energy due to their inappropriate placements. In this paper we present a low time-complexity heuristic mapping algorithm of weighted application graph under permissible bandwidth constraint to minimize communication energy of 2-D mesh-based NoC architecture. The experimental results of multimedia benchmarks, as well as randomly generated samples show the low communication energy as well as time-complexity under bandwidth constraints in comparison to the recent heuristic application mapping approaches. In our approach, the communication energy is also close to the optimal solution obtained by Integer Linear Programming (ILP).     

Scalability limits of Bag-of-Tasks applications running on hierarchical platforms

Bag-of-Tasks applications are parallel applications composed of independent (i.e., embarrassingly parallel) tasks, which do not communicate with each other, may depend upon one or more input files, and can be executed in any order. Each file may be input for more than one task. Examples of Bag-of-Tasks (BoT) applications include Monte Carlo simulations, massive searches (such as key breaking), image manipulation applications and data mining algorithms. A common framework to execute BoT applications is the master-slave topology, in which the user machine is used to control the execution of tasks. In this scenario, a large number of concurrent tasks competing for resources (e.g., CPU and communication links) severely limits application execution scalability. This paper is devoted to study the scalability of BoT applications running on multi-node systems (such as clusters and multi-clusters) organized as hierarchical platforms, considering several communication paradigms. Our study employs a set of experiments that involves the simulation of various large-scale platforms. The results presented provide important guidelines for improving the scalability of practical applications.     

Multiobjective optimization and evolutionary algorithms for the application mapping problem in multiprocessor system-on-chip design

Sesame is a software framework that aims at developing a modeling and simulation environment for the efficient design space exploration of heterogeneous embedded systems. Since Sesame recognizes separate application and architecture models within a single system simulation, it needs an explicit mapping step to relate these models for cosimulation. The design tradeoffs during the mapping stage, namely, the processing time, power consumption, and architecture cost, are captured by a multiobjective nonlinear mixed integer program. This paper aims at investigating the performance of multiobjective evolutionary algorithms (MOEAs) on solving large instances of the mapping problem. With two comparative case studies, it is shown that MOEAs provide the designer with a highly accurate set of solutions in a reasonable amount of time. Additionally, analyses for different crossover types, mutation usage, and repair strategies for the purpose of constraints handling are carried out. Finally, a number of multiobjective optimization results are simulated for verification.     

Distributed multirobot exploration, mapping, and task allocation

We present an integrated approach to multirobot exploration, mapping and searching suitable for large teams of robots operating in unknown areas lacking an existing supporting communications infrastructure. We present a set of algorithms that have been both implemented and experimentally verified on teams—of what we refer to as Centibots—consisting of as many as 100 robots. The results that we present involve search tasks that can be divided into a mapping stage in which robots must jointly explore a large unknown area with the goal of generating a consistent map from the fragment, a search stage in which robots are deployed within the environment in order to systematically search for an object of interest, and a protection phase in which robots are distributed to track any intruders in the search area. During the first stage, the robots actively seek to verify their relative locations in order to ensure consistency when combining data into shared maps; they must also coordinate their exploration strategies so as to maximize the efficiency of exploration. In the second and third stages, robots allocate search tasks among themselves; since tasks are not defined a priori, the robots first produce a topological graph of the area of interest and then generate a set of tasks that reflect spatial and communication constraints. Our system was evaluated under extremely realistic real-world conditions. An outside evaluation team found the system to be highly efficient and robust.     

Pods – A novel intelligent energy efficient and dynamic frequency scalings for multi-core embedded architectures in an IoT environment

In the Advent of the Internet of Things (IoT), embedded architecture takes an important dimension in terms of energy and accomplishment. The embedded system needs more and more intelligent algorithms for better performance and energy efficiency to fit into an IoT scenario. Moreover, with the existence of high-performance multi-core embedded architectures, achievements of energy efficiency remains in the dark side of the research. Several algorithms such as dynamic frequency scaling, thread mapping, starvation methodologies were proposed in embedded architectures for efficient usages of clock frequencies and these features were used as the energy saving modes in which the consumption of energy in the embedded architectures are being controlled. But these methods have several backlogs which permits the use of consumption in the embedded architectures. Considering the above features, this paper proposes a new methodology PODS(Predictors for Optimized Dynamic Scaling) which integrates a powerful machine learning algorithm for scaling the clock frequencies by the input workloads and allocation of the core depending based on the workload. The proposed framework PODS has different phases of working namely workload extraction, characterization, and optimization using BAT algorithms and prediction extreme Machine - Learning. The algorithm was tested on ARM/Cortex architectures (Raspberry Pi 3 Model B+), an evaluated algorithm using the IoMT benchmarks and various parameters that include energy consumption, accuracy of detection/prediction was determined and analyzed. It is found that the implementation of the proposed framework in the test is seen resulting between 35 and 40% reduction in the consumption of the power.