ABSTRACT We present a 1,024‐FPGA DES supercomputer accelerator that is automatically compiled from a single‐threaded sequential DES key search application by means of our High‐Level Synthesis compiler. Our 1,024‐FPGA supercomputer is deployed on several Amazon Web Services (AWS) EC2 F1 instance platforms from different AWS regions. Consequently, it can be considered the first multi‐chip application‐specific supercomputer that is scattered to multiple geographically distributed data centers around the world. Furthermore, invoking our 1,024‐FPGA DES supercomputer is functionally identical to invoking the single‐threaded sequential DES application the supercomputer accelerator is compiled from. Our 1,024‐FPGA supercomputer achieves 3.016E+12 keys/sec and it performs 5,286,000 times better than an AWS EC2 m5.8xlarge Xeon x86 machine executing the original sequential application with a performance of 5.706 E+5 keys/sec.

Summary Hardware‐accelerated cloud computing systems based on FPGA or ASIC chips have proved useful in providing power‐efficient acceleration for a variety of software applications. However, these computing systems rely on operating systems and hypervisors, which not only are implemented with inefficient software, but which also are incapable of handling massively parallel systems, due to the lack of parallelism and scalability in their algorithmic designs. As a result, power, performance, and scalability problems will emerge in an exascale cloud computing environment. As a solution to these problems, the present study proposes a parallel hardware hypervisor system implemented entirely in special‐purpose hardware without resorting to energy‐inefficient general‐purpose processors. Furthermore, the proposed hypervisor system virtualizes application‐specific multi‐chip supercomputers, in order to enable the virtual supercomputers to share available FPGA and semi‐configurable ASIC resources in a cloud system. Single‐chip verification studies based on Verilog simulation have been done to verify the functional correctness of the proposed hardware hypervisor system, which consumes only a fraction of hardware resources. This article will in particular focus on the virtualization of multi‐chip message‐passing based supercomputers using limited reconfigurable hardware resources.

Hardware-accelerated cloud computing systems based on FPGA chips (FPGA cloud) or ASIC chips (ASIC cloud) have emerged as a new technology trend for power-efficient acceleration of various software applications. However, the operating systems and hypervisors currently used in cloud computing will lead to power, performance, and scalability problems in an exascale cloud computing environment. Consequently, the present study proposes a parallel hardware hypervisor system that is implemented entirely in special-purpose hardware, and that virtualizes application-specific multi-chip supercomputers, to enable virtual supercomputers to share available FPGA and ASIC resources in a cloud system. In addition to the virtualization of multi-chip supercomputers, the system’s other unique features include simultaneous migration of multiple communicating hardware tasks, and on-demand increase or decrease of hardware resources allocated to a virtual supercomputer. Partitioning the flat hardware design of the proposed hypervisor system into multiple partitions and applying the chip unioning technique to its partitions, the present study introduces a cloud building block chip that can be used to create FPGA or ASIC clouds as well. Single-chip and multi-chip verification studies have been done to verify the functional correctness of the hypervisor system, which consumes only a fraction of (10%) hardware resources.

Data communication stack on Internet of Things (IoT)-devices is traditionally implemented in software as a part of their operating systems. In IoT-applications for which resource constrained IoT-devices are deployed, leveraging microprocessor(s) for both computing and data communication tasks may result in poor application performance and high power consumption. In order to alleviate these performance and power issues, using System on Chip (SoC) field programmable gate arrays (FPGAs) for the hardware acceleration of the performance- or power-critical software tasks is a recent, popular trend in the literature. On the other hand, constrained application protocol (CoAP) is a pivotal network protocol for many IoT-applications. Motivated by these facts, in this article, a hardware accelerator for a CoAP server network stack is proposed and realized on a SmartFusion2 SoC FPGA. The hardware accelerated CoAP server network stack is thoroughly evaluated and compared in terms of its performance, latency, power consumption, and FPGA resource utilization against a baseline software implemented CoAP server network stack. The evaluation results obtained clearly show that the CoAP hardware accelerator provides significantly higher performance and lower response message latency, while consuming significantly less power. Consequently, the CoAP hardware accelerator proposed seems to be a strong viable solution for the resource constrained IoT-devices.

Among various approaches to eye tracking systems, light-reflection based systems with non-imaging sensors, e.g., photodiodes or phototransistors, are known to have relatively low complexity; yet, they provide moderately accurate estimation of the point of gaze. In this paper, a low-computational approach on gaze estimation is proposed using the Eye Touch system, which is a light-reflection based eye tracking system, previously introduced by the authors. Based on the physical implementation of Eye Touch, the sensor measurements are now utilized in low-computational least-squares algorithms to estimate arbitrary gaze directions, unlike the existing light reflection-based systems, including the initial Eye Touch implementation, where only limited predefined regions were distinguished. The system also utilizes an effective pattern classification algorithm to be able to perform left, right, and double clicks based on respective eye winks with significantly high accuracy. In order to avoid accuracy problems for sensitive sensor biasing hardware, a robust custom microcontroller-based data acquisition system is developed. Consequently, the physical size and cost of the overall Eye Touch system are considerably reduced while the power efficiency is improved. The results of the experimental analysis over numerous subjects clearly indicate that the proposed eye tracking system can classify eye winks with 98% accuracy, and attain an accurate gaze direction with an average angular error of about 0.93 °. Due to its lightweight structure, competitive accuracy and low-computational requirements relative to video-based eye tracking systems, the proposed system is a promising human-computer interface for both stationary and mobile eye tracking applications.

In this study, a new eye tracking system, namely Eye Touch, is introduced. Eye Touch is based on an eyeglasses-like apparatus on which IrDA sensitive sensors and IrDA light sources are mounted. Using inexpensive sensors and light sources instead of a camera leads to lower system cost and need for the computation power. A prototype of the proposed system is developed and tested to show its capabilities. Based on the test results obtained, Eye Touch is proved to be a promising human-computer interface system.

The static staging heuristics proposed in the literature for staging the data items associated with real-time distributed applications adhere to a method by which only one data item is transferred in each communication step to optimize a specific cost function. In this paper, we first propose the Extended Partial Path (EPP) algorithm based on the same method. In terms of maximizing the number of satisfied requests, we have analytically shown that EPP has a performance that is equal to or greater than the Partial Path Heuristic (PPH) introduced previously [CHECK END OF SENTENCE], thanks to excluding the data items that cannot be satisfied by PPH from scheduling and scheduling the satisfiable data-items along their extended paths. In contrast to EPP and other data staging heuristics proposed, we develop the concurrent scheduling (CS) heuristic which allows simultaneous transfer of more than one data item in an organized fashion, thereby improving the overall performance of the staging system. At the heart of the CS heuristic are EPP and the local priority assignment method devised for solving the conflicts between data items at the intermediate nodes. The extensive simulation results further confirm the superiority of the CS heuristic over PPH.

A heterogeneous computing (HC) system is composed of a suite of geographically distributed high-performance machines interconnected by a high-speed network, thereby providing high-speed execution of computationally intensive applications with diverse demands. In HC systems, however, there is a possibility of machine and network failures and this can have an adverse impact on applications running on the system. In order to decrease the impact of failures on an application, matching and scheduling algorithms must be devised which minimize not only the execution time but also the failure probability of the application. However, because of the conflicting requirements, it is not possible to minimize both at the same time. Thus, the goal of this paper is to develop matching and scheduling algorithms which account for both the execution time and the failure probability and can trade off execution time against the failure probability of the application. In order to attain these goals, a biobjective scheduling problem is first formulated and then two different algorithms, the biobjective dynamic level scheduling algorithm and the biobjective genetic algorithm, are developed. Unique to both algorithms is the expression used for computing the failure probability of an application with precedence constraints. The simulation results confirm that the proposed algorithms can be used for producing task assignments where the execution time is weighed against the failure probability.

Large-scale data intensive applications with real-time requirements are currently emerging in many disciplines of science and engineering. Such applications can benefit from a grid environment provided that an efficient solution to the following data scheduling problem can be found: schedule the transfer of a set of large-scale data objects of distributed applications in a grid environment so as to meet real-time constraints associated with these data transfers. Based on this premise, This work focuses on the aforementioned problem and proposes a new effective path-selection based scheduling algorithm. The algorithm performs its optimization based on a schedule reflection model; a new cost criterion that takes into account the satisfiability of each application as a whole. We show, by simulation, that our algorithm improves the performance of data intensive real-time applications.

Summary form only given. The problem of scheduling a set of independent tasks (a metatask) with multiple QoS needs, such as timeliness, reliability, versions, security and priority, in a heterogeneous computing (HC) environment is referred to as the QoS-based scheduling problem. Several heuristics have been proposed in the literature to solve the QoS-based scheduling problem, which is proven to be NP-hard. Selecting the best heuristic to use in a given HC environment is not trivial, since each heuristic makes different assumptions about the underlying QoS model. This article performs a comparative study of five such heuristics, namely QSMTS-IP, min-min, genetic algorithm, least slack first and sufferage. The heuristics have been modified from their original implementations to incorporate additional QoS attributes, the notion of service-types and to enable them to be simulated using a common set of assumptions. The study provides a fair basis for comparison of these heuristics, for tasks with varied service-types (hard, soft or best-effort) for each QoS dimension and varied degrees of tightness of task deadlines. The heuristics are outlined, the QoS-model is defined and the simulation environment is described. The simulation study shows how each heuristic performs in terms of number of satisfied users, makespan and total utility. The results provide suggestions on which heuristic is best suited for conditions prevailing in a particular HC environment.

Finding an optimal solution to the problem of scheduling an application modeled by a directed acyclic graph (DAG) onto a set of heterogeneous machines is known to be an NP-hard problem. In this study, we present a duplication based scheduling algorithm, namely the levelized duplication based scheduling (LDBS) algorithm, which solves this problem efficiently. The primary goal of LDBS is to minimize the schedule length of applications. LDBS can accommodate different duplication heuristics, thanks to its modular design. Specifically, we have designed two different duplication heuristics with different time complexities. The simulation studies confirm that LDBS is a very competitive scheduling algorithm in terms of minimizing the schedule length of applications.

Providing quality of service (QoS) to high bandwidth video, voice and data applications in wireless networks is an important problem. Such applications are in the class of real-time applications; they need communication operations to complete within certain targeted deadlines. Based on this premise, this paper addresses the design of distributed MAC layer protocols that incorporate explicit support for real-time traffic in an ad-hoc wireless network. Specifically, we have developed two new MAC layer protocols, namely the elimination by sieving (ES-DCF) and the deadline bursting (DB-DCF) protocols. Both algorithms use deterministic collision resolution algorithms in order to provide timely delivery guarantees to different classes of real-time traffic. The extensive simulation studies conducted confirmed that ES-DCF and DB-DCF perform well for hard-real-time traffic and soft-real-time traffic, respectively.

In a heterogeneous distributed computing system, machine and network failures are inevitable and can have an adverse effect on applications executing on the system. To reduce the effect of failures on an application executing on a failure-prone system, matching and scheduling algorithms which minimize not only the execution time but also the probability of failure of the application must be devised. However, because of the conflicting requirements, it is not possible to minimize both of the objectives at the same time. Thus, the goal of this paper is to develop matching and scheduling algorithms which account for both the execution time and the reliability of the application. This goal is achieved by modifying an existing matching and scheduling algorithm. The reliability of resources is taken into account using an incremental cost function proposed in this paper and the new algorithm is referred to as the reliable dynamic level scheduling algorithm. The incremental cost function can be defined based on one of the three cost functions developed here. These cost functions are unique in the sense that they are not restricted to tree-based networks and a specific matching and scheduling algorithm. The simulation results confirm that the proposed incremental cost function can be incorporated into matching and scheduling algorithms to produce schedules where the effect of failures of machines and network resources on the execution of the application is reduced and the execution time of the application is minimized as well.

This paper investigates the problem of matching and scheduling of an application, which is composed of tasks with precedence constraints, to minimize both execution time and probability of failure of the application in a heterogeneous computing system. In general, however, it is impossible to satisfy both objectives at the same time because of conflicting requirements. The best one can do is to trade off execution time for reliability or vice versa, according to users' needs. Furthermore, there is a need for an algorithm which can assign tasks of an application to satisfy both of the objectives to some degree. Motivated from these facts, two different algorithms, which are capable of trading off execution time for reliability, are developed. To enable the proposed algorithms to account for the reliability of resources in the system, an expression which gives the reliability of the application under a given task assignment is derived. The simulation results are provided to validate the performance of the proposed algorithms.

In this paper, two cost functions that can be incorporated into a matching and scheduling algorithm for tasks with precedence constraints are introduced to enable the algorithm to consider the reliability of different resources in the system while making decisions. The cost functions introduced are unique in the sense that they are not restricted to tree-based networks and a specific matching and scheduling algorithm. As an example, cost functions are applied to a compile time, static list scheduling heuristic. The simulation results confirm that the proposed cost functions can be exploited to produce task assignments where the effect of failures of machines and network resources on the execution of the application is reduced.

This paper presents a novel technique for routing in wormhole-switched multiprocessor interconnection networks with clustered configuration. The network model used here consists of a set of clusters interfaced through a common central network. We assume that the central network and the clusters use independent algorithms to route messages between their internal nodes. A technique for deriving a global routing algorithm based on the local algorithms is presented, which allows the transfer of messages between any pair of nodes in the network. This proposed method is shown to be deadlock-free with two virtual channels. The clustered network model and the proposed routing technique can be used to enhance the fault tolerance capability of existing routing algorithms. In particular, we describe fault-tolerant routing methods for meshes, which can tolerate any arbitrary fault distribution without disabling connected healthy nodes.