Probabilistic reasoning models (PMs) and probabilistic inference bring advantages when dealing with small datasets or uncertainty on the observed data, and allow to integrate expert knowledge and create interpretable models. The main challenge of using these PMs in practice is that their inference is very compute-intensive. Therefore, custom hardware architectures for the exact and approximate inference of PMs have been proposed in the SotA. The throughput, energy and area efficiency of approximate PM inference accelerators are strongly dominated by the sampler blocks required to sample arbitrary discrete distributions. This paper proposes and studies novel discrete sampler architectures towards efficient and flexible hardware implementations for PM accelerators. Both cumulative distribution table (CDT) and Knuth-Yao (KY) based sampling algorithms are assessed, based on which different sampler hardware architectures were implemented. Innovation is brought in terms of a reconfigurable CDT sampling architecture with a flexible range and a reconfigurable Knuth-Yao sampling architecture that supports both flexible range and dynamic precision. All architectures are benchmarked on real-world Bayesian Networks, demonstrating up to 13 × energy efficiency benefits and 11 × area efficiency improvement of the optimized reconfigurable Knuth-Yao sampler over the traditional linear CDT-based samplers used in the PM SotA.

A growing number of applications like probabilistic machine learning, sparse linear algebra, robotic navigation, etc., exhibit irregular data flow computation that can be modeled with directed acyclic graphs (DAGs). The irregularity arises from the seemingly random connections of nodes, which makes the DAG structure unsuitable for vectorization on CPU or GPU. Moreover, the nodes usually represent a small number of arithmetic operations that cannot amortize the overhead of launching tasks/kernels for each node, further posing challenges for parallel execution. To enable energy-efficient execution, this work proposes DAG processing unit (DPU) version 2, a specialized processor architecture optimized for irregular DAGs with static connectivity. It consists of a tree-structured datapath for efficient data reuse, a customized banked register file, and interconnects tuned to support irregular register accesses. DPU-v2 is utilized effectively through a targeted compiler that systematically maps operations to the datapath, minimizes register bank conflicts, and avoids pipeline hazards. Finally, a design space exploration identifies the optimal architecture configuration that minimizes the energy-delay product. This hardware-software co-optimization approach results in a speedup of $1.4 \times, 3.5 \times $, and $14 \times $ over a state-of-the-art DAG processor ASIP, a CPU, and a GPU, respectively, while also achieving a lower energy-delay product. In this way, this work takes an important step towards enabling an embedded execution of emerging DAG workloads.

Sparse, irregular graphs show up in various applications like linear algebra, machine learning, engineering simulations, robotic control, etc. These graphs have a high degree of parallelism, but their execution on parallel threads of modern platforms remains challenging due to the irregular data dependencies. The execution performance can be improved by efficiently partitioning the graphs such that the communication and thread synchronization overheads are minimized without hurting the utilization of the threads. To achieve this, this article proposesGraphOpt, a tool that models the graph parallelization as a constrained optimization problem and uses the open Google OR-Tools solver to find good partitions. Several scalability techniques are developed to handle large real-world graphs with millions of nodes and edges. Extensive experiments are performed on the graphs of sparse matrix triangular solves (linear algebra) and sum-product networks (machine learning), respectively, showing a mean speedup of 2.0× and 1.8× over previous state-of-the-art libraries, demonstrating the effectiveness of the constrained-optimization-based graph parallelization.

Probabilistic reasoning is an essential tool for robust decision-making systems because of its ability to explicitly handle real-world uncertainty, constraints and causal relations. Consequently, researchers are developing hybrid models by combining Deep Learning with probabilistic reasoning for safety-critical applications like self-driving vehicles, autonomous drones, etc. However, probabilistic reasoning kernels do not execute efficiently on CPUs or GPUs. This paper, therefore, proposes a custom programmable processor to accelerate sum-product networks, an important probabilistic reasoning execution kernel. The processor has an optimized datapath architecture and memory hierarchy optimized for sum-product networks execution. Experimental results show that the processor, while requiring fewer computational and memory units, achieves a 12x throughput benefit over the Nvidia Jetson TX2 embedded GPU platform.

Methods that learn the structure of Probabilistic Sentential Decision Diagrams (PSDD) from data have achieved state-of-the-art performance in tractable learning tasks. These methods learn PSDDs incrementally by optimizing the likelihood of the induced probability distribution given available data and are thus robust against missing values, a relevant trait to address the challenges of embedded applications, such as failing sensors and resource constraints. However PSDDs are outperformed by discriminatively trained models in classification tasks. In this work, we introduce D-LearnPSDD , a learner that improves the classification performance of the LearnPSDD algorithm by introducing a discriminative bias that encodes the conditional relation between the class and feature variables.

Bayesian reasoning is a powerful mechanism for probabilistic inference in smart edge-devices. During such inferences, a low-precision arithmetic representation can enable improved energy efficiency. However, its impact on inference accuracy is not yet understood. Furthermore, general-purpose hardware does not natively support low-precision representation. To address this, we propose ProbLP, a framework that automates the analysis and design of low-precision probabilistic inference hardware. It automatically chooses an appropriate energy-efficient representation based on worst-case error-bounds and hardware energy-models. It generates custom hardware for the resulting inference network exploiting parallelism, pipelining and low-precision operation. The framework is validated on several embedded-sensing benchmarks.

Smart portable applications increasingly rely on edge computing due to privacy and latency concerns. But guaranteeing always-on functionality comes with two major challenges: heavily resource-constrained hardware; and dynamic application conditions. Probabilistic models present an ideal solution to these challenges: they are robust to missing data, allow for joint predictions and have small data needs. In addition, ongoing efforts in field of tractable learning have resulted in probabilistic models with strict inference efficiency guarantees. However, the current notions of tractability are often limited to model complexity, disregarding the hardware's specifications and constraints. We propose a novel resource-aware cost metric that takes into consideration the hardware's properties in determining whether the inference task can be efficiently deployed. We use this metric to evaluate the performance versus resource trade-off relevant to the application of interest, and we propose a strategy that selects the device-settings that can optimally meet users' requirements. We showcase our framework on a mobile activity recognition scenario, and on a variety of benchmark datasets representative of the field of tractable learning and of the applications of interest.

The deep convolutional neural network (DCNN) is a class of machine learning algorithms based on feed-forward artificial neural network and is widely used for image processing applications. Implementation of DCNN in real-world problems needs high computational power and high memory bandwidth, in a power-constrained environment. A general purpose CPU cannot exploit different parallelisms offered by these algorithms and hence is slow and energy inefficient for practical use. We propose a field-programmable gate array (FPGA)-based runtime programmable coprocessor to accelerate feed-forward computation of DCNNs. The coprocessor can be programmed for a new network architecture at runtime without resynthesizing the FPGA hardware. Hence, it acts as a plug-and-use peripheral for the host computer. Caching is implemented for input features and filter weights using on-chip memory to reduce the external memory bandwidth requirement. Data are prefetched at several stages to avoid stalling of computational units and different optimization techniques are used to efficiently reuse the fetched data. Dataflow is dynamically adjusted in runtime for each DCNN layer to achieve consistent computational throughput across a wide range of input feature sizes and filter sizes. The coprocessor is prototyped using Xilinx Virtex-7 XC7VX485T FPGA-based VC707 board and operates at 150 MHz. Experimental results show that our implementation is energy efficient than highly optimized CPU implementation and achieves consistent computational throughput of more than 140 G operations/s for a wide range of input feature sizes and filter sizes. Off-chip memory transactions decrease by due to the use of the on-chip cache.

Floorplanning, as an early stage of the physical design flow, has been extensively studied in literature and developed into several branches. Recently, hierarchical floorplanning is regaining attention due to the rising scale of systems-on-chip, which necessarily requires divide-and-conquer strategies to handle the increasing complexity. This paper introduces a floorplanning scheme targeting hierarchical physical prototyping, answering some of the questions posed by Kahng [8] on classical floorplanning. Our scheme emphasizes practical requirements including runtime scalability, wire length and shape quality. We formulate a new hierarchical floorplanning problem with reduced computational complexity, but without weakening the problem as a global layout optimization. To achieve this goal, a placement seed is taken as input and converted into a slicing floorplan under the given constraints of region area and aspect ratio (region shape). We solve the problem by devising an efficient slicing algorithm with integrated dynamic programming. Implementation of the algorithm shows fast runtime and good quality of result.

Twenty years ago a paper detailing a novel neural network, called ADAM and that could be directly implemented in hardware RAM, was published in the first conference of this series. Subsequent research based directly/indirectly on this type of RAM-based neural network founded a research group that has produced over 200 research documents. This paper overviews that research and goes on to mathematically define a CMML, a generalised version of a CMM (the component at the heart of ADAM). The CMML can be trained to replicate the exact computational properties of a CMM and so is a plug-and-play replacement to a CMM; whilst a different training algorithm gives it different properties when used in recall.

This book describes theoretical results about AnsProlog * that have been obtained over the past decade.AnsProlog * or Prolog with Answer Sets 1 is a variation of the Prolog programming language, and extends the language by allowing clauses of the form:in the program.The L i 's are the literals (or atoms) of the Prolog language and may be supplied with a prefix ¬ sign, indicating the negation of a literal, while the prefix of not indicates negation as failure.Hence the semantics of the clause (C) may be read as follows: if all the literals L1, . . ., L m are true and all the literals L m+1 , . . ., L n can be safely assumed false then at least one of the literals L 1 , . . ., L k is true.(The actual semantics of each AnsProlog * program will be defined in terms of the Herbrand Universe of ground terms and the Herbrand Base of ground atoms.)The book takes the approach that the clause (C) is the most general form of a clause in the AnsProlog * language and so various subclasses of AnsProlog * can be defined by restricting this clause.For example: an AnsProlog -not program is when none of the clauses of a program contain the prefix not.In this respect, the book discusses the tractability, the complexity, the expressibility of the various subclasses of AnsProlog * based on the premise that AnsProlog * is both an excellent knowledge representation language and that it has a number of advantages over the Prolog language implementations based on SLDNF.For example, the ordering of goals within a clause and the ordering of clauses within a Prolog program affects whether a solution can or cannot be found (i.e. the program might get into an infinite loop); but not this is not the case within an AnsProlog * program.The reason being is that the semantics of an implementation of the AnsProlog * language can be thought of as allowing all models of the program to exist and then by using the clauses within the program, to impose restrictions on these models.The actual model(s) produced can then be interpreted in either a bi-valent (where a ground atom is either true or false) fashion or a tri-valent (where a ground atom is either true, false or unknown) fashion.The implementation algorithms describing how to restrict the models are described in Chapter 7 and two systems implementing the AnsProlog * language (and various subclasses), viz: (i) lparse+smodels and (ii) dlv are discussed in Chapter 8.The lparse+smodels program produces the stable models (or bi-valent) implementation, while the dlv produces the well-founded models (or tri-valent) implementation.Baral does note that both systems are under development and so implying that Chapter 8 may be out of date within a few years.However this aspect is compensated by Baral having a website www.baral.us/bookonewhere hypertext links to both the two systems and an errata/additional notes for the book are presented.On the application side, the book is peppered with many examples and simple programs illustrating the current point being made in the text.For example: how various forms of the 1 AnsProlog * is sometimes called A-Prolog in the literature.

This book describes theoretical results about AnsProlog * that have been obtained over the past decade.AnsProlog * or Prolog with Answer Sets 1 is a variation of the Prolog programming language, and extends the language by allowing clauses of the form:in the program.The L i 's are the literals (or atoms) of the Prolog language and may be supplied with a prefix ¬ sign, indicating the negation of a literal, while the prefix of not indicates negation as failure.Hence the semantics of the clause (C) may be read as follows: if all the literals L1, . . ., L m are true and all the literals L m+1 , . . ., L n can be safely assumed false then at least one of the literals L 1 , . . ., L k is true.(The actual semantics of each AnsProlog * program will be defined in terms of the Herbrand Universe of ground terms and the Herbrand Base of ground atoms.)The book takes the approach that the clause (C) is the most general form of a clause in the AnsProlog * language and so various subclasses of AnsProlog * can be defined by restricting this clause.For example: an AnsProlog -not program is when none of the clauses of a program contain the prefix not.In this respect, the book discusses the tractability, the complexity, the expressibility of the various subclasses of AnsProlog * based on the premise that AnsProlog * is both an excellent knowledge representation language and that it has a number of advantages over the Prolog language implementations based on SLDNF.For example, the ordering of goals within a clause and the ordering of clauses within a Prolog program affects whether a solution can or cannot be found (i.e. the program might get into an infinite loop); but not this is not the case within an AnsProlog * program.The reason being is that the semantics of an implementation of the AnsProlog * language can be thought of as allowing all models of the program to exist and then by using the clauses within the program, to impose restrictions on these models.The actual model(s) produced can then be interpreted in either a bi-valent (where a ground atom is either true or false) fashion or a tri-valent (where a ground atom is either true, false or unknown) fashion.The implementation algorithms describing how to restrict the models are described in Chapter 7 and two systems implementing the AnsProlog * language (and various subclasses), viz: (i) lparse+smodels and (ii) dlv are discussed in Chapter 8.The lparse+smodels program produces the stable models (or bi-valent) implementation, while the dlv produces the well-founded models (or tri-valent) implementation.Baral does note that both systems are under development and so implying that Chapter 8 may be out of date within a few years.However this aspect is compensated by Baral having a website www.baral.us/bookonewhere hypertext links to both the two systems and an errata/additional notes for the book are presented.On the application side, the book is peppered with many examples and simple programs illustrating the current point being made in the text.For example: how various forms of the 1 AnsProlog * is sometimes called A-Prolog in the literature.