Whether one or multiple hardware execution units are activated (i.e. CPU cores), invalid resource sharing, notably due to simultaneous accesses, proves to be problematic as it can yield to unexpected runtime behaviors with negative implications such as security or safety issues. The growing interest for off-the-shelf multi-core architectures in sensitive applications motivates the need for safe resources sharing. If critical sections are a well-known solution from imperative and non-temporized programming models, they fail to provide safety guarantees. By leveraging the time-triggered programming model, this paper aims at enforcing that identified critical windows of computations can never be simultaneously executed. We achieve this result by determining, before an application is compiled, the exact dates during which a task accesses a shared resource, which enables the off-line validation of non-simultaneity constraints.

Pointer aliasing still hinders compiler optimizations. The ISO C standard 99 has added the restrict keyword that allows programmer to specify non-aliasing as an aid to the compiler's optimizer. The task of annotating pointers with the restrict keyword is still left to the programmer and this task is, in general, tedious and prone to errors. Scalar replacement is an optimization widely used by compilers. In this paper, we present two new Frama-C plug-ins, RECKA for automatic annotation of CUDA kernels arguments with the restrict keyword, and RPromF for scalar replacement in OpenACC and OpenMP 4.0/4.5 codes for GPU. More specifically, RECKA works as follows: (i) an alias analysis is performed on CUDA kernels and their callers; (ii) if not found any alias then CUDA kernels are cloned, the clones are renamed and their arguments are annotated with the restrict qualifier; and (iii) instructions are added to kernels call sites to perform at runtime a less-than check analysis on kernel actuals parameters and determine if the clone must be called or the original one. RPromF includes five main steps: (i) OpenACC/OpenMP offloading regions are identified; (ii) functions containing these offloading codes and their callers are analyzed to check that there is no alias; (iii) if there is no alias then the offloading codes are cloned; (iv) clone's instructions are analyzed to retrieve data reuse information and perform scalar replacement; and instructions are added to be able to use the optimized clone whenever possible. We have evaluated the two plug-ins on PolyBench benchmark suite. The results show that both scalar replacement and the usage of restrict keyword are effective for improving the overall performance of OpenACC, OpenMP 4.0/4.5 and CUDA codes.

The development of Advanced Driver Assistance Systems (ADAS), such as pedestrian detection, requires real-time update rates at high image resolution. Hopefully, heterogeneous architectures with high computing performance have been developed for this purpose. To benefit from this hardware performance, different programming languages and acceleration frameworks have been developed. OpenVX framework provides a graph-based execution model to program image processing algorithms on heterogeneous platforms. In this work, we investigate OpenVX optimizations for computer vision applications. We examine how this framework responds to different data access patterns. We test three important optimizations of OpenVX: kernels merge, data tiling and parallelization via OpenMP. The contribution and the impact of each optimization on different data access pattern are explained.

Monocular motion analysis for advanced driver assistance systems (ADAS) is a very active research topic. However, two constraints limit the implementation of existent techniques in autonomous vehicles: poorly textured regions and large displacements due to vehicle egomotion that both lead to matching ambiguities. Coarse-to-fine strategies are generally used to deal with large motion, but the lack of large texture makes this approach inefficient to estimate road relative displacement. In this paper, we propose to assist the optical flow process by exploiting both a 3D scene model and a rough velocity estimate from either other embedded sensors or egomotion estimations from the previous frames. Using the available a priori knowledge allows to compensate the dominant flow to facilitate the estimation of the remaining part by a classical optical flow method. We give results on both synthetic and real image sequences and compare our approach to other existing methods.

Research community has developed numerous SLAM (Simultaneous Localization And Mapping) algorithms in the last ten years. These algorithms are widely used by autonomous robots operating in unknown environments. Several works have presented many algorithms' optimizations. New computing technologies (SIMD coprocessors, multi-cores) can greatly accelerate the system processing but require rethinking the algorithm implementation. This paper presents an efficient implementation of the EKF-SLAM algorithm on a multicore architecture. The algorithm-architecture adequacy aims to optimize the implementation of the SLAM algorithm on a low-cost architecture (Dual-core and Dual SIMD coprocessor). Experiments were conducted with an instrumented platform. Results aim to demonstrate that an optimized implementation of the algorithm, resulting from an evaluation methodology, can help to design embedded systems implementing low-cost multicore architecture operating under real time constraints.

The need for computing power drastically increases and one good solution is to use many-core architectures. Besides, complex embedded applications become data-dependent and their execution time depends on their input data. For this reason, on-line task and data allocation is needed to optimize the architecture efficiency. Moreover, communications are a complex problem in many-core architectures. Because of dynamic allocation, communication paths and network loads become unpredictable, which must be handled by the network. This paper proposes an evaluation of different network topologies in terms of performance and area for many-core architectures. It concludes that hierarchical networks are the best trade-off. In particular, the MultiCross topology is 10 times more efficient than the mesh topology.

One of the major challenges of multicore architectures is not only to aim toward high performance but also to efficiently harness the computing power of these systems. This is especially true for embedded systems where problems of energy and silicon efficiencies are critical. Multicore architectures provide significant gains for explicitly multi-threaded or dataflow applications. However, single-task applications commonly found in embedded systems do not fit well with current multicore architectures. To maximize performance and efficiency of the chip, communication and allocation-synchronization problems need to be addressed in concert with a coherent and carefully crafted approach of the programming interface. This paper focuses on allocation-synchronization problems and the programming interface of these architectures. The proposed mechanism is based on an intermediate level of parallelism and provides a solution for allocating and synchronizing processing cores with an easy to use instruction set architecture. This mechanism avoids global synchronization of cores when interruptions or exceptions occur on the main processor. This increases core utilizations among all applications executed on the chip and thus, chip efficiency. A preliminary evaluation has shown significant improvements in terms of performance, energy and silicon efficiencies of the chip.

The need for computing power drastically increases and one solution is to use MPSoC. These MPSoCs become complex with the increase of the number of cores. Thus, designers use simulators to explore the whole platform parameters in order to define the best architecture. These simulators must be fast and accurate whatever is the architecture complexity. This paper introduces a new approximate-timed TLM approach to provide a speed up of at least x100 on the simulation time in comparison with a timed TLM approach. This new communication method allows fast and accurate hardware parameter exploration of MPSoC with a standard SystemC protocol. The lack of accuracy in networks-on-chip can affect the execution order, but the opposite slows down simulation and cannot support MPSoC exploration. For this reason, this paper focuses on networks-on-chip to demonstrate the benefits of our approximate-timed TLM approach.

Many basic computations can be done by means of iterative neighborhood-based calculations, including threshold, optimum, distance transform, contour closing, mathematical morphology, etc. Some of them can be performed using rows-per-rows scans (A. Rosenfeld and J.-L. Pfaltz, 1966) (G. Borgefors, 1986). Such regular computations allow to optimize the use of caches on standard architecture, and to achieve computations in good times. However, these basic computations are also useful inside the regions of the images. When applied on some regions instead of the whole image, more scans could be necessary because of the irregular shape of the regions. In this paper, we show that row-per-row scans can be used for a large class of operators, so-called idempotent r-operators (including the previously cited computations). Moreover, we give conditions on the use of scans to perform neighborhood-based computations inside any regions. Among other results, we show that only two scans allow to compute a distance transform in every regions used in classical split and merge algorithms (S.L. Horowitz and T. Pavlidis, 1976), and only three scans are sufficient on Voronoi regions (M. Tuceryan and A.K. Jain, 1990). These results extend the use of row per row scans to more cases, and improve many algorithms that rely on some neighborhood-based computations inside regions.

This article describes a new strategy for analyzing contours in static images. The goal of this analysis is to find the interest centres in the images and then to explain some common optical illusion phenomena. The approach proposed is based on a modified version of the Ant Colony Optimization paradigm named Ant Scan (here introduced). Ant Scan is different from the ACO meta-heuristic principally in the mechanism of exploration of the interest space (the image to be analyzed). Experimental results have shown that interactions among these new agents (based on communication by pheromone) can generate another type of emergent phenomenon that can be utilized to explain how human beings process static images. Classical optical illusions have been analyzed with this new model and a qualitative explanation of how they act is provided.

Many works have been done for parallelizing low-level image analysis computations. However the task is harder for higher levels, as the data manipulations are complex, and there is a wide range of algorithms to encompass. To allow concurrently speed and programmability, a high-level programming model that can be efficiently implemented on parallel architectures is required. To achieve this goal, we propose the associative nets model, a parallel computing model for image analysis based on simple data-parallelism paradigms, providing special features, such as graph-based data structures to handle irregular data, virtual data-structures to ease hierarchical image descriptions, and specific primitives (dirassoc) to compute on the interpixels relation graph. For implementation purposes, the dirassoc computing primitive performs asynchronous local computations until it reaches stability. Asynchronism has many advantages for hardware (speed, power consumptions, and chip size) as well as in software (less synchronization barriers). However to insure completion of the asynchronous operation, the dirassoc must use a set of specific operators (r-operators) introduced by Ducourthial. In this paper we emphasize on the interest of the r-operators and of the asynchronous computations for image analysis algorithms. We give applications in distance transforms, contour closing, Voronoi segmentation, watershed segmentation, and mathematical morphology. Hence, we show that asynchronous computations are powerful tools for image analysis on interpixel graphs.

This paper presents a new parallel computing model called Associative Nets. This model relies on basic primitives called associations that consist of applying an associative operator over connected components of a subgraph of the physical interprocessor connection graph. Associations can be very efficiently implemented (in terms of hardware cost or processing time) thanks to asynchronous computation. This model is quite effective for image analysis and several other fields; as an example, graph processing algorithms are presented. While relying on a much simpler architecture, these algorithms have, in general, a complexity equivalent to the one obtained by more expensive computing models, like the PRAM model.

This paper presents a new scheme for software support of image analysis. It extends the data parallel programming model with the notion of connected component. Thanks to a graph based model, called associative nets, connected component manipulations can be expressed in terms global object-based transformations. This model has been embedded in the Pacco interactive image analysis environment and allows flexible handling of regions and contours, as illustrated by a set of examples.

The recent application of fractal techniques is a significant development in image compression. These fractal methods provide very high compression ratios for natural scenes. Fractal methods have the advantage of being resolution independent. However, their encoding complexity is O(n/sup 4/) for an n/spl times/n pixel image. This prohibits their real-time application. We propose a massively parallel implementation on a pyramid machine that yields a considerable speedup. This implementation reduces the fractal encoding complexity to O(n/sup 2/). Our parallel method has much better performance than other existing methods.>

This paper presents a new reconfigurable architecture for image analysis: the associative mesh. This architecture provides powerful computational primitives that can apply an associative operator over the connex sets of a graph. These primitives can be easily and efficiently realised in hardware by means of asynchronous operations and are adapted to a large number of image analysis primitives. As an example, the implementation of distance transforms is described.

Quadtree region representation, image properties computation of binary image and moment invariants are implemented on a pyramid machine. Based on those algorithms a parallel pattern recognition technique is proposed. Exploiting the parallel quadtree representation on pyramid machine, moment invariants seems to be a good descriptor in a hierarchical coarse-fine matching strategy. For a particular image, the moment invariants always changes slightly at higher levels in the representation. A matching criteria of distance measure can be used to find dissimilarity in images.>

Finding a parallel architecture adapted to a given class of algorithms is a central problem for architects. This paper presents a methodology to realize it, and provides an illustration using image analysis. First, we show a set of common basic operations that can be used to solve most image analysis problems. Then these movements are translated to fit some natural communications in a given architecture. The considered data movements (global operations on connected pixel sets) can express a large class of algorithms. Their implementation on exemplary massively parallel architectures (arrays, hypercubes, pyramids) is discussed.