Exploring the DataFlow Supercomputing Paradigm

We propose a new method of graph partitioning for big graphs that include a conceptual schema. The conceptual schema of a graph database, called a schema graph, is defined implicitly as part of the graph database itself. A graph database is stored in a distributed triple-store, i.e., a distributed database system for managing graph edges represented by triples. We define the statistics of a graph database on the basis of the schema graph. The statistics are gathered for all schema triples, i.e., the types of graph edges. The space of the schema triples is partially ordered by the is-more-general relationship that is defined through the class and predicate taxonomies. The graph partitioning method has two phases. A skeleton graph of the triple-store is computed in the first phase. The skeleton graph is composed of the set of schema triples that have the extensions of an appropriate size to serve as the fragments of the distribution. The edges of the skeleton graph are selected in a top-down manner, i.e., from the most general schema triple to more specific schema triples. The edges of the skeleton graph are clustered into n partitions in the second phase of the algorithm. The function distance that is used in the clustering algorithm is based on the statistics of the schema triples. The graph partitioning function maps each schema triple from the skeleton graph to its partition, stored on a separate data server. The partitioning function is well defined in that it maps the types of the triple-patterns to k fragments such that k corresponds to the size of the portions of the triple-store addressed by the triple-patterns. In other words, it maps the types of triple-patterns that address a large number of triples to multiple distributed fragments, and the types of triple-patterns that address few triples to a single fragment.

Control-flow computer architectures are based on the von Neumann paradigm. They are flexible enough to support the execution of instructions in any order. Each instruction is fetched from the memory before it could be executed. Passing the data from the instruction that produces it to the instruction that requires it is done using registers or memory. DataFlow computer architectures are configured for execution of an algorithm, while data travel through the hardware. They are suitable for high-performance computing, where the same set of instructions should be run many times. Initialization of data and other processing is done by the processor based on control-flow. The Maxeler framework provides functionality for transforming any algorithm into a VHDL file, and further configuring the dataflow hardware. It also provides support for sending data from the control-flow host processor to the dataflow hardware, and bringing results back. Common programming languages are supported for the host processor, while dataflow hardware programming is done in MaxJ, which is an extended subset of the Java programming language. One can use an integrated development environment called MaxIDE, which is based on Eclipse. We present here a perspective overview of a cloud-supported web-based integrated development environment, WebIDE, which is a subset of MaxIDE, and enables users to develop and run programs for dataflow hardware even without owning dataflow hardware. The main concepts are explained, as well as differences in two integrated development environments. Then, our main focus is on the point of view of programmers, and the goal is to compare the MaxIDE and the WebIDE Maxeler framework, describing the technology needed to support the WebIDE Maxeler framework, providing that the MaxIDE already exists.

In this chapter, we will showcase a new approach to the calculation of the extrema of functions in one dimension by implementing the golden-section search algorithm using the dataflow paradigm. This paradigm has been around for quite some time already, but it was only recently, with the increased need to compute large datasets, that its use was brought to attention to many scientists around the globe. BigData has always been present to an extent, but with the ever-growing industry and the increasing speed in which information multiplies by the minute, the models that follow these changes have been expanding as well. Many fields use mathematical models as a way of explanation of various systems. These models are usually composed of equations whose number is counted in thousands. Too often it is needed to calculate the extrema of functions that those equations represent. Doing this the traditional way by using the control-flow paradigm shows that the majority of execution time is spent on calculation. In this chapter, we would like to show that this process can be sped up, and thus, leave more time to perform other actions regarding the exploration of the modeled systems.

The focus of this chapter is on algorithms for dataflow computer architecture, which use matrices and vectors as the underlying data structure. DataFlow algorithms usually run as an optimized part of a classical control-flow procedure, which includes reading, writing, and other manipulation of data in such a way that it is easily processed by the dataflow part. Such data handling is usually referred to as data choreography and, in order to obtain an efficient algorithm, it must be appropriately examined. Our main goal is to describe various data choreographies that may be used when streaming matrices to a dataflow engine. Additionally, we have performed an experimental evaluation of these choreographies while using them with algorithms for various matrix-based computational problems. Finally, we have also given an overview of how several problems have been solved from graph theory using matrix multiplication as the basis.

An algorithm for spherical code design, based on the variable repulsion force method is presented. The iterative nature of the algorithm and the large number of operations it performs make it suitable for implementation on dataflow supercomputing devices. Gains in computation speed and power consumption of such an implementation are given. Achieved minimum distances and simulated error probabilities of obtained codes are presented.

Face recognition has its theoretical and practical value in daily life. In this chapter, we will present face recognition application and discuss its implementation using the Maxeler DataFlow paradigm. We first give theoretical background and overview of the existing solutions in the area of algorithms for face recognition. Maxeler card is based on FPGA technology and therefore a brief explanation of the main FPGA characteristics are given and the comparison is made with GPU technology. After that, we analyze one of the PCA algorithms called Eigenface for its application, first on PC and then on Maxeler card. The results show that this algorithm is suitable for implementing on Maxeler card using the dataflow paradigm. By analyzing aforementioned algorithm, it could be seen that execution timing could be reduced, which is especially important when working with large databases. We could conclude that the use of the Maxeler DataFlow paradigm provides advantages in comparison to PC application, resulting in reduction in memory access latency and increase in power efficiency, due to the execution of instructions in natural sequence as data propagates through the algorithm. Since there are many technical challenges (e.g., viewpoint, lightening, facial expression, different haircut, presence of glasses, hats, etc.) affecting successful recognition, this area is to be further examined and algorithms could be adapted for dataflow implementation.

Image segmentation is one of the most common procedures in medical imaging applications. It is also very important task in breast cancer detection. Breast cancer detection procedure based on mammography can be divided into several stages. The first stage is the extraction of region of interest from a breast image, after which the identification of suspicious mass regions, their classification, and comparison with the existing image database follows. It is often the case that already existing image databases have large sets of data for which processing requires a lot of time, thus the acceleration of each of the processing stages in breast cancer detection is a very important issue. Image filtering is also one of the most common and important tasks in image processing applications. It is, in most cases, preprocessing procedure for 3D visualization of an image stack. In order to achieve high-quality 3D visualization of a 2D image stack, it is of particular importance that all the images of the input stack are clear and sharp, thus their filtering should be executed carefully. There are also many algorithms for 3D visualization, so it is important to choose the right one which will execute fast enough and produce satisfied quality. In this chapter, the implementation of the already existing algorithm for region-of-interest-based image segmentation for mammogram images on High-Performance Reconfigurable DataFlow Computers (HPRDC) is proposed. As a DataFlow Engine (DFE) of such HPRDC, Maxeler’s acceleration card is used. The experiments for examining the acceleration of that algorithm on the Reconfigurable DataFlow Computers (RDC) are performed with two types of mammogram images with different resolutions. There were, also, several DFE configurations and each of them gave different acceleration of algorithm execution. Those accelerations are presented and experimental results have been shown good acceleration. Also, image processing using a mean filtering algorithm combined with thresholding and binarization algorithms and 3D visualization of murine lungs using marching cubes method are explained. These algorithms are mapped on the Maxeler’s DFE to significantly increase calculation speed. Optimal algorithm calculation speed was up to 20-fold baseline calculation speed.

This chapter presents a wide spectrum of the dataflow implementations of applications in physics simulations. All the examples are uniformly presented, which makes possible an easy design and performance comparison among the presented dataflow algorithms.

Bitcoin, which is known as the world’s first decentralized peer-to-peer payment network and cryptocurrency, introduced a decentralized mining process, where miners compete in confirming transactions in order to earn a certain amount of digital coins (bitcoins). Bitcoin mining is a repetitive and highly parallelizable process, and thus suitable for parallel computing. In this chapter, we present Maxeler dataflow paradigm as a form of parallel computing to process big data with low energy consumption and explain our dataflow implementation of the bitcoin mining algorithm for Maxeler MAX2B and MAX5C dataflow computers. With our dataflow design, we achieved up to 102 times faster and up to 256 times more energy-efficient bitcoin mining compared to standard multicore CPUs (Central Processing Units). While Maxeler dataflow computers are not able to compete against ASIC (Application-Specific Integrated Circuit) bitcoin mining rigs in terms of hash rate and energy efficiency, they are flexible and can be reprogrammed to do other tasks, while ASIC mining rigs are fixed (running only one specific algorithm) and usually become outdated in a few months.