Search

The objective of the traveling salesperson problem (TSP) is to find a shortest tour through all nodes in a graph. Euclidean TSPs are traditionally represented with “cities” placed on a 2D plane. When straight line obstacles are added to the plane, a tour has to visit all cities while going around obstacles. The resulting problem with obstacles remains metric, but is not Euclidean because the shortest paths are no longer straight lines. We first revise a previous version of multiresolution graph pyramid by modifying the hierarchical clustering stage. Next, we describe two new experiments with human subjects. In the first experiment, the effect of the length of obstacles on the quality of tours produced by subjects was tested with three problem sizes. Long obstacles affect the tours to a greater degree than short obstacles, but long obstacles create obvious clusters and limit the ways in which the tours can be produced. In the second experiment we evaluated the degree to which Multidimensional Scaling (MDS) can compensate for the presence of obstacles. The results show that although MDS approximation can compensate to a large degree for the presence of obstacles, it cannot fully account for human performance. This fact suggests that mental representation of a TSP with obstacles is not Euclidean. Instead, it is likely to be based on hierarchical clustering in which pairwise distances represent the shortest paths around obstacles.

Remote computing has emerged as a trendy computing model that enables users to process an immense number of computations efficiently on the remote server where the necessary data and high-performance computing power are provisioned. Unfortunately, despite such an advantage, this computing model suffers from insider threats that are committed by adversarial administrators of remote servers who attempt to steal or corrupt users’ private data. These security threats are somewhat innate to remote computing in that there is no means to control administrators’ unlimited data access. In this paper, we present our novel hardware-centric solution, called MeetGo, to address the intrinsic threats to remote computing. MeetGo is a field-programmable gate array (FPGA)-based trusted execution environment (TEE) that aims to operate independently of the host system architecture. To exhibit the ability and effectiveness of MeetGo as a TEE ensuring secure remote computing, we have built two concrete applications: cryptocurrency wallet and GPGPU. MeetGo provides a trust anchor for these applications that enable their users to trade cryptocurrency or to run a GPGPU program server on a remote server while staying safe from threats by insiders. Our experimental results clearly demonstrate that MeetGo incurs only a negligible performance overhead to the applications.

This, paper presents the FISH (FPGA-Initiated Software-Handled) framework which allows FPGA accelerators to make system calls to the Linux operating system in CPU-FPGA systems. A special FISH Linux kernel module running on the CPU provides a system call interface for FPGA accelerators, much like the ABI which exists for software programs. We provide a proof-of-concept implementation of this framework running on the Intel Cyclone V SoC device, and show that an FPGA accelerator can seamlessly make system calls as if it were the host program. We see the FISH framework being especially useful for high-level synthesis (HLS) by making it possible to synthesize software code that contains system calls.

We describe new multi-ported cache designs suitable for use in FPGA-based processor/parallel-accelerator systems, and evaluate their impact on application performance and area. The baseline system comprises a MIPS soft processor and custom hardware accelerators with a shared memory architecture: on-FPGA L1 cache backed by off-chip DDR2 SDRAM. Within this general system model, we evaluate traditional cache design parameters (cache size, line size, associativity). In the parallel accelerator context, we examine the impact of the cache design and its interface. Specifically, we look at how the number of cache ports affects performance when multiple hardware accelerators operate (and access memory) in parallel, and evaluate two different hardware implementations of multi-ported caches using: 1) multi-pumping, and 2) a recently-published approach based on the concept of a live-value table. Results show that application performance depends strongly on the cache interface and architecture: for a system with 6 accelerators, depending on the cache design, speed up swings from 0.73× to 6.14×, on average, relative to a baseline sequential system (with a single accelerator and a direct-mapped, 2KB cache with 32B lines). Considering both performance and area, the best architecture is found to be a 4-port multi-pump direct-mapped cache with a 16KB cache size and a 128B line size.

Resource sharing is a key area-reduction approach in high-level synthesis (HLS) in which a single hardware functional unit is used to implement multiple operations in the high-level circuit specification. We show that the utility of sharing depends on the underlying FPGA logic element architecture and that different sharing trade-offs exist when 4-LUTs vs. 6-LUTs are used. We further show that certain multi-operator patterns occur multiple times in programs, creating additional opportunities for sharing larger composite functional units comprised of patterns of interconnected operators. A sharing cost/benefit analysis is used to inform decisions made in the binding phase of an HLS tool, whose RTL output is targeted to Altera commercial FPGA families: Stratix IV (dual-output 6-LUTs) and Cyclone II (4-LUTs).