Integrating traffic cameras with deep learning facilitates real-time multi-camera vehicle path reconstruction, benefiting smart city initiatives such as traffic management and public safety. The high demands on latency, bandwidth, and privacy underscore the necessity of edge computing platforms. However, the continuous operation of compute-intensive deep learning algorithms on round-the-clock camera streams can exceed the compute and power capacities of edge data centers. Therefore, it is critical to strategically deploy and activate camera streams to balance compute demands with performance requirements. Currently, there is a lack of tools to support this planning process. This paper presents Seer, a comprehensive suite of tools and algorithms that aids traffic planners in optimizing traffic camera placement and deep learning model deployment, considering compute and budgetary constraints. Seer encompasses (1) a graph-based algorithm for efficient camera placement incorporating road network topology, (2) a collaborative algorithm for vehicle path reconstruction that enables the use of less accurate but resource-efficient deep learning models, and (3) a scalable traffic simulation framework derived from open-source projects that model city road networks. Evaluations of Seer on two real-world road networks, each with thousands of intersections and simulated vehicle paths, show a 6.3x reduction in compute requirements. This is achieved through a combination of sparse camera deployment and the use of lightweight models, with an average 55% increase in the Hausdorff distance for the path reconstruction algorithm, translating to an absolute increase of 135 to 195 meters.

This paper proposes a scalable distributed video analytics framework that can process thousands of video streams from sources such as CCTV cameras using semantic scene analysis. The main idea is to deploy deep learning pipelines on the fog nodes and generate semantic scene description records (SDRs) of video feeds from the associated CCTV cameras. These SDRs are transmitted to the cloud instead of video frames saving on network bandwidth. Using these SDRs stored on the cloud database, we can answer many complex queries and perform rich video analytics, within extremely low latencies. There is no need to scan and process the video streams again on a per query basis. The software architecture on the fog nodes allows for integrating new deep learning pipelines dynamically into the existing system, thereby supporting novel analytics and queries. We demonstrate the effectiveness of the system by proposing a novel distributed algorithm for real-time vehicle pursuit. The proposed algorithm involves asking multiple spatio-temporal queries in an adaptive fashion to reduce the query processing time and is robust to inaccuracies in the deployed deep learning pipelines and camera failures.

The popularity of High-Frequency Trading (HFT) or algorithmic trading has surged in the last ten years, largely due to the exponential increase in computing power. However, while software solutions for HFT have become increasingly optimized over time, they are still plagued by network stack, and kernel-user space separation overheads. Order book construction is a crucial step in any HFT system, as it provides a market snapshot on which trading decisions must be based and executed. This paper proposes a simple linear data structure for tracking the order book and a hybrid binary-linear search algorithm to maintain the top bid and ask offers corresponding to market depth, on FPGAs. Our approach takes into account that most trading activity occurs on the top of the bid and offer sides. Through design analysis and experimentation, we demonstrate that our simple approach is scalable and practical, outperforming previous methods.

The exponential performance growth guaranteed by Moore’s law has started to taper in recent years. At the same time, emerging applications like image processing demand heavy computational performance. These factors inevitably lead to the emergence of domain-specific accelerators (DSA) to fill the performance void left by conventional architectures. FPGAs are rapidly evolving towards becoming an alternative to custom ASICs for designing DSAs because of their low power consumption and a higher degree of parallelism. DSA design on FPGAs requires careful calibration of the FPGA compute and memory resources towards achieving optimal throughput. Hardware Descriptive Languages (HDL) like Verilog have been traditionally used to design FPGA hardware. HDLs are not geared towards any domain, and the user has to put in much effort to describe the hardware at the register transfer level. Domain Specific Languages (DSLs) and compilers have been recently used to weave together handwritten HDLs templates targeting a specific domain. Recent efforts have designed DSAs with image-processing DSLs targeting FPGAs. Image computations in the DSL are lowered to pre-existing templates or lower-level languages like HLS-C. This approach requires expensive FPGA re-flashing for every new workload. In contrast to this fixed-function hardware approach, overlays are gaining traction. Overlays are DSAs resembling a processor, which is synthesized and flashed on the FPGA once but is flexible enough to process a broad class of computations through soft reconfiguration. Less work has been reported in the context of image processing overlays. Image processing algorithms vary in size and shape, ranging from simple blurring operations to complex pyramid systems. The primary challenge in designing an image-processing overlay is maintaining flexibility in mapping different algorithms. This paper proposes a DSL-based overlay accelerator called FlowPix for image processing applications. The DSL programs are expressed as pipelines, with each stage representing a computational step in the overall algorithm. We implement 15 image-processing benchmarks using FlowPix on a Virtex-7-690t FPGA. The benchmarks range from simple blur operations to complex pipelines like Lucas-Kande optical flow. We compare FlowPix against existing DSL-to-FPGA frameworks like Hetero-Halide and Vitis Vision library that generate fixed-function hardware. On most benchmarks, we see up to 25% degradation in latency with approximately a 1.7x to 2x increase in the FPGA LUT consumption. Our ability to execute any benchmark without incurring the high costs of hardware synthesis, place-and-route, and FPGA re-flashing justifies the slight performance loss and increased resource consumption that we experience. FlowPix achieves an average frame rate of 170 FPS on HD frames of 1920 × 1080 pixels in the implemented benchmarks.

Increasingly, pre-trained convolutional neural networks (CNNs) are being deployed for inference in various computer vision applications, both on the server-side in the data centers and at the edge. CNN inference is a very compute-intensive task. It is a challenge to meet performance metrics such as latency and throughput while optimizing power. Special-purpose ASICs and FPGAs are suitable candidates to meet these power and performance budgets simultaneously. Rapidly evolving CNN architectures involve novel convolution operations such as point convolutions, depth separable convolutions, and so on. This leads to substantial variation in the computational structure across CNNs and layers within a CNN. Because of this, FPGA reconfigurability provides an attractive tradeoff compared to ASICs. FPGA-based hardware designers address the structural variability issue by generating a network-specific accelerator for a single network or a class of networks. However, homogeneous accelerators are network agnostic and often sacrifice throughput and FPGA LUTs for flexibility. In this article, we propose an FPGA overlay for efficient processing of CNNs that can be scaled based on the available compute and memory resources of the FPGA. The overlay is configured on the fly through control words sent by the host on a per-layer basis. Unlike current overlays, our architecture exploits all forms of parallelism inside a convolution operation. A constraint system is employed at the host end to find out the per-layer configuration of the overlay that uses all forms of parallelism in the processing of the layer, resulting in the highest throughput for that layer. We studied the effectiveness of our overlay by using it to process AlexNet, VGG16, YOLO, MobileNet, and ResNet-50 CNNs targeting a Virtex7 and a bigger Ultrascale+VU9P FPGAs. The chosen CNNs have a mix of different types of convolution layers and filter sizes, presenting a good variation in model size and structure. Our accelerator reported a maximum throughput of 1,200 GOps/second on the Virtex7, an improvement of 1.2 \( \times \) to 5 \( \times \) over the recent designs. Also, the reported performance density, measured in giga operations per second per KLUT, is 1.3 \( \times \) to 4 \( \times \) improvement over existing works. Similar speed-up and performance density is also observed for the Ultrascale+VU9P FPGA.

Unlike CPUs and GPUs, it is possible to use custom fixed-point data types, specified as a tuple (α, β), on FPGAs. The parameters α and β denote the number of integral and fractional bitwidths respectively. The power and area savings while performing arithmetic operations on fixed-point data types are well known to be significant over using floating-point data types.

Images when processed using various enhancement techniques often lead to edge degradation and other unwanted artifacts such as halos. These artifacts pose a major problem for photographic applications where they can denude the quality of an image. There is a plethora of edge-aware techniques proposed in the field of image processing. However, these require the application of complex optimization or post-processing methods. Local Laplacian Filtering is an edge-aware image processing technique that involves the construction of simple Gaussian and Laplacian pyramids. This technique can be successfully applied for detail smoothing, detail enhancement, tone mapping and inverse tone mapping of an image while keeping it artifact-free. The problem though with this approach is that it is computationally expensive. Hence, parallelization schemes using multi-core CPUs and GPUs have been proposed. As is well known, they are not power-efficient, and a well-designed hardware architecture on an FPGA can do better on the performance per watt metric. In this paper, we propose a hardware accelerator, which exploits fully the available parallelism in the Local Laplacian Filtering algorithm, while minimizing the utilization of on-chip FPGA resources. On Virtex-7 FPGA, we obtain a 7.5x speed-up to process a 1 MB image when compared to an optimized baseline CPU implementation. To the best of our knowledge, we are not aware of any other hardware accelerators proposed in the research literature for the Local Laplacian Filtering problem.

In this paper, we propose a fully parallel and pipelined architecture for stereo vision on FPGAs using Semi-Global Matching with Census Transform being used underneath. Further, we extend the above streaming architecture so that multiple pixels can be processed in a data parallel fashion. We expose this data parallelism through dependency relaxation. This establishes a trade-off between accuracy and throughput of the hardware. We tested the proposed architecture on Virtex-7 FPGA using KITTI 2012 and KITTI 2015 datasets. On images of resolution 1280x960, with 64 disparity levels, we are able to run our hardware design at 100 MHz. At this frequency, our design is able to process 322 frames per second which is 1.6 times faster than the state-of-the-art SGM implementation on FPGA. Our system can be scaled to a higher resolution image.

Model checking is now a standard technology for verifying large and complex systems. While there are a range of tools and techniques to verify various properties of a system under consideration, in this work, we restrict our attention to safety checking procedures using explicit state space generation. The necessary hardware resources required in this approach depends on the model complexity and the resulting state transition graph that gets generated. This cannot be estimated apriori. For reasonably realistic models, the available main memory in even high end servers may not be sufficient. Hence, we have to use distributed safety verification approaches on a cluster of nodes. However, the problem of estimating the minimum number of nodes in the cluster for the verification procedure to complete successfully remains unsolved. In this paper, we propose a dynamically scalable model checker using an actor based architecture. Using the proposed approach, an end user can invoke a model checker hosted on a cloud platform in a push button fashion. Our safety verification procedures automatically expands the cluster by requesting more virtual machines from the cloud provider. Finally, the user gets to pay only for the hardware resources he rented for the duration of the verification procedure. We refer to this as Model Checking as Service. We approach this problem by proposing an asynchronous algorithm for safety checking in actor framework. The actor based approach allows for scaling the resources on a need basis and redistributes the work load transparently through state migration. We tested our approach by developing a distributed version of SpinJA model checker using Akka actor framework. We conducted our experiments on Google Cloud Engine (GCE) platform wherein we scale our resources automatically using the GCE API. On large models such as anderson.8 from BEEM benchmark suite, our approach reduced the model checking cost in dollars by 8.6x while reducing the wall clock time to complete the safety checking procedure 5.5x times.

Time-sharing, which allows for multiple users to use a shared resource, is an important and fundamental aspect of modern computing systems. However, accelerators such as GPUs, that come without a native operating system do not support time sharing. The inability of accelerators to support time-sharing limits their applicability especially as they get deployed in Platform-as-a-Service and Resource-as-a-Service environmen ts. In the former, elastic demands may require preemption where as in the latter, fine-grained economic models of service cost can be supported with time sharing. In this paper, we extend the concept of time sharing to the GPGPU computational space using cooperative multitasking approach. Our technique is applicable to any GPGPU program written in Compute Unified Device Architecture (CUDA) API provided for C/C++ programming languages. With minimal support from the programmer, our framework incorporates process scheduling, light-weight memory management, and multi-GPU support. Our framework provides an abstraction where, in a round-robin manner, every workload can use a GPU(s) over a time quantum exclusively. We demonstrate the applicability of our scheduling framework, by running many workloads concurrently in a time sharing manner.

This paper describes an automatic approach to accelerate image processing pipelines using FPGAs. An image processing pipeline can be viewed as a graph of interconnected stages that processes images successively. Each stage typically performs a point-wise, stencil, or other more complex operations on image pixels. Recent efforts have led to the development of domain-specific languages (DSL) and optimization frameworks for image processing pipelines. In this paper, we develop an approach to map image processing pipelines expressed in the PolyMage DSL to efficient parallel FPGA designs. Our approach exploits reuse and available memory bandwidth (or chip resources) maximally. When compared to Darkroom, a state-of-the-art approach to compile high-level DSL to FPGAs, our approach (a) leads to designs that deliver significantly higher throughput, and (b) supports a greater variety of filters. Furthermore, the designs we generate obtain an improvement even over pre-optimized FPGA implementations provided by vendor libraries for some of the benchmarks.

A high-level synthesis compiler translates a source program written in a high level programming language such as C or SystemC into an equivalent circuit. The performance of the generated circuit in terms of metrics such as area, frequency and clock cycles depends on the compiler optimizations enabled and their order of application. Finding an optimal sequence for a given program is a hard combinatorial optimization problem. In this paper, we propose a practical and search time efficient technique for finding a near-optimal sequence for a given program. The main idea is to strike a balance between the search for a universally good sequence (like that of O3) which works for all programs vis-a-vis finding a good sequence on a per-program basis. Towards that, we construct a rich downsampled sequence set, which caters to different program classes, from the unbounded optimization sequence space by applying heuristic search algorithms on a set of Microkernel benchmark programs. The optimization metric that we use while constructing the downsampled sequence set is the execution time on a scalar processor. Given a new program, we try all the sequences from the downsampled sequence setand pick the best. Applying this technique in the LegUp high-level synthesis compiler, we are able to obtain 23% and 40% improvement on CHStone and Machsuite benchmark programs respectively. We also propose techniques to further reduce the size of the downsampled sequence set to improve the sequence search time.

In this paper, we propose a hybrid CPU+GPU data structure, that optimizes search operation for frequently accessed search keys. This is based on the working-set structure due to Badiu et al. [1]. The main idea is to maintain a dynamic set of most frequently accessed keys in the GPU memory and the rest of the keys in the CPU main memory. Further, search queries are processed in batches of size 1K to 16K (K = 210). We measured the query throughput of our data structure using Millions of Queries Processed per Second (MQPS) as a metric, on different key access distributions. On distributions, where some keys are accessed more frequently than others, we achieved 2x higher MQPS when compared to a highly tuned hash map provided by C++ BOOST library, and 1.5x higher MQPS against the B+ tree implementation in the Rodinia GPU benchmark. We further showed the effectiveness of our structure, when it is used to store visited vertices information in breadth-first search traversal of graphs. Here, we achieved 1.2x and 1.5x speedups when compared to the BOOST hash map and the GPU B+ trees respectively.

Software is finding place in deeply embedded systems to large scale distributed systems of cloud service providers such as Amazon and Google. Due to the concurrent and distributed nature of this software, it is hard to test for correctness of such systems in a foolproof manner. Explicit state model checking is an approach in which we build a model of the system and specify the properties it should hold. Then we construct a state transition system from the model and check if it satisfies the specified properties. There are two kinds of properties of interest: safety and liveness. In this paper, we focus our attention on safety verification, which involves checking if the states that are generated in the transition system satisfy some predicate formulae specified in the form of assertions. The main problem here is that the number of states in the transition system grows exponentially with the number of bits required to store the state of a model at any given point time. So the available main memory even in a server class machine is not sufficient to model check non-trivial practical models. One approach to address this problem is by using resources from a distributed collection of machines. In this paper, we adopt this approach, by proposing a distributed safety property verification algorithm using the vertex centric programming model.

The memory and core requirements of a virtual machine depend on the performance requirements of the applications hosted on it. In this paper, we propose algorithms for dynamic memory and core scaling using a combination of machine learning and feedback control techniques. These algorithms work for sequential and parallel applications such as scientific computations where speedup is the primary performance metric. Then we use these algorithms to address the simultaneous memory and core allocation problem, which is more complex due to possible correlation between these resource requirements. All these algorithms can be applied in a black box fashion without instrumenting the source code of applications.

Today, IaaS cloud providers are dynamically minimizing the cost of data centers operations, while maintaining the Service Level Agreement (SLA). Currently, this is achieved by the live migration capability, which is an advanced state-of-the-art technology of Virtualization. However, existing migration techniques suffer from high network bandwidth utilization, large network data transfer, large migration time as well as the destination's VM failure during migration. In this paper, we propose Reliable Lazy Copy (RLC) - a fast, efficient and a reliable migration technique. RLC provides a reasonable solution for high-efficiency and less disruptive migration scheme by utilizing the three phases of the process migration. For effective network bandwidth utilization and reducing the total migration time, we introduce a learning phase to estimate the writable working set (WWS) prior to the migration, resulting in an almost single time transfer of the pages. Our approach decreases the total data transfer by 1.16 x - 12.21x and the total migration time by a factor of 1.42x - 9.84x against the existing approaches, thus providing a fast and an efficient, reliable VM migration of the VMs in the cloud.

The compiler optimizations we enable and the order in which we apply them on a program have a substantial impact on the program execution time. Compilers provide default optimization sequences which can give good program speedup. As the default sequences have to optimize programs with different characteristics, they embed in them multiple subsequences which can optimize different classes of programs. These multiple subsequences may falsely interact with each other and affect the potential program speedup achievable. Instead of searching for a single universally optimal sequence, we can construct a small set of good sequences such that for every program class there exists a near-optimal optimization sequence in the good sequences set. If we can construct such a good sequences set which covers all the program classes in the program space, then we can choose the best sequence for a program by trying all the sequences in the good sequences set. This approach completely circumvents the need to solve the program classification problem. Using a sequence set size of around 10 we got an average speedup up to 14% on PolyBench programs and up to 12% on MiBench programs. Our approach is quite different from either the iterative compilation or machine-learning-based prediction modeling techniques proposed in the literature so far. We use different training and test datasets for cross-validation as against the Leave-One-Out cross-validation technique.

This paper shows a complete upward collapse in the Polynomial Hierarchy (PH) if for ZPP, two queries to a SAT oracle is equivalent to one query. That is, ZPPSAT[1]= ZPPSAT||[2]rArr ZPPSAT[1]= PH. These ZPP machines are required to succeed with probability at least 1/2 + 1/p(n) on inputs of length n for some polynomial p(n). This result builds upon recent work by Tripathi who showed a collapse of PH to S2P. The use of the probability bound of 1/2 + 1/p(n) is justified in part by showing that this bound can be amplified to 1 - 2-nkfor ZPPSAT[1]computations. This paper also shows that in the deterministic case, PSAT[1]= PSAT||[2]rArr PH sube ZPPSAT[1]where the ZPPSAT[1]machine achieves a probability of success of 1/2 - 2-nk.

The NP machine hypothesis posits the existence of an \in \ge 0 and a nondeterministic polynomial-time Turing machine M which accepts the language 0 but for which no deterministic Turing machine running in 2^n time can output an accepting path infinitely often. This paper shows two applications of the NP machine hypothesis in bounded query complexity. First, if the NP machine hypothesis holds, then P^SAT[1] = P^SAT[2] \Rightarrow PH \subseteq NP. Without assuming the NP machine hypothesis, the best known collapse of the Polynomial Hierarchy (PH) is to the class S_2^P due to a result of Fortnow, Pavan and Sengupta [9]. The second application is to bounded query function classes. If the NP machine hypothesis holds then for all constants d \ge 0, there exists a constant k \ge d such that for all oracles X, PF^SAT[n^k] \not\subset PF^X[n^d]. In particular, PF^SAT[n^d] \varsubsetneq PF^SAT[n^k]. Without the NP machine hypothesis, there are currently no known consequences even if for all k \ge 1, PF^SAT[n^k] \subseteq PF^SAT[n].