In the given technology-driven era, smart cities are the next frontier of technology, and these smart cities aim to improve the quality of people’s lives. In this article, we introduce such future Internet of Things (IoT)-based smart cities that leverage blockchain technology. Particularly, when there are multiple parties involved, blockchain helps in improving the security and transparency of the system in an efficient manner. However, if a current fee-based or first-come–first-serve-based processing is used, emergency events may get delayed and even threaten people’s lives. Thus, there is a need for transaction prioritization based on the priority of information and a dynamic block creation mechanism for efficient data recording and faster event response. Also, our system focuses on the consortium blockchain maintained by a group of members working across different organizations to provide more efficiency. The leader election procedure in such a consortium blockchain becomes more important for the transaction prioritization process to take place honestly. Hence, in our proposed consensus protocol, we deploy a machine-learning (ML) algorithm to achieve efficient leader election, based on which a novel dynamic block creation algorithm is designed. Also, to ensure the honest block generation behavior of the leader, a peer-prediction-based verification mechanism is proposed. Both security analysis and simulation experiments are carried out to demonstrate the robustness, accuracy, and efficiency of our proposed scheme.

Smart cities have become a trend with improved efficiency, resilience, and sustainability, providing citizens with high quality of life. With the increasing demand for a more participatory and bottom–up governance approach, citizens play an active role in the process of policy making, revolutionizing the management of smart cities. In the example of urban infrastructure maintenance, the public participation demand is more remarkable as the infrastructure condition is closely related to their daily life. Although blockchain has been widely explored to benefit data collection and processing in smart city governance, public engagement remains a challenge. In this article, we propose a novel public participation consortium blockchain system for infrastructure maintenance that is expected to encourage citizens to actively participate in the decision-making process and enable them to witness all administrative procedures in a real-time manner. To that aim, we introduced a hybrid blockchain architecture to involve a verifier group, which is randomly and dynamically selected from the public citizens, to verify the transaction. In particular, we devised a private-prior peer-prediction-based truthful verification mechanism to tackle the collusion attacks from public verifiers. Then, we specified a Stackelberg-game-based incentive mechanism for encouraging public participation. Finally, we conducted extensive simulations to reveal the properties and performances of our proposed blockchain system, which indicates its superiority over other variations.

Blockchain is a distributed ledger technology based on the underlying peer-to-peer network. In this paper, we focus on improving the chances of a transaction being packaged into a valid block so as to be recorded on the main chain. Blockchain nodes typically broadcast transactions they receive to the whole network. Hence, for recording transactions on the blockchain more efficiently, it becomes essential to determine influential nodes to publish transactions, where influential nodes are more actively involved in mining, recording, or broadcasting transactions in the network. To that aim, we propose an Influential Node Determination Framework (INDF) using a series of significant factors, such as hash rate, latency, active time, and degree of a node. Specifically, INDF consists of two parallel schemes: the first scheme figures out influential pools according to their hash rates where a truth-telling mechanism design is employed to encourage the pool nodes to report their true hash rate values; the second one determines influential individual nodes based on an improved L-H index algorithm. Remarkably, the proposed truth-telling mechanism is proved to be incentive-compatible. Our improved L-H index algorithm is comparatively studied to reflect the impacts of different node parameters on the node’s ranking. Extensive experiments are conducted to demonstrate the effectiveness of our proposed framework.

Due to the continuous, unbounded, and dynamic characteristics of the streaming data, mining data streams becomes a very challenging task. When analyzing online data streams, it is necessary to produce accurate results in a very short amount of time. The parallel processing power of Graphics Processing Units (GPUs) can be used to accelerate the processing and produce results in a timely manner. In this paper, we present GStreamMiner, a GPU-accelerated data stream mining framework and demonstrate its application using outlier detection over continuous streaming data as a case study. The demo software provides a visual interface which is continuously get updated with new results as the data stream progresses. It also facilitates the users to compare the performance of the GPU and CPU versions of the outlier detection algorithm.

Outlier detection or anomaly detection is applied in numerous applications, such as fraud detection, network intrusion detection, manufacturing, and environmental monitoring. Due to the continuous and dynamic characteristics of streaming data, outlier detection over data streams becomes a very challenging task. When analyzing real-time data streams, it is typically impossible to store the entire set of data due to space limitations. Also due to the high data rates, it is necessary to produce the results in a limited amount of time. Parallel processing power of Graphics Processing Units (GPUs) can be used to accelerate the outlier detection process, and thus address the challenges of outlier detection over data streams. This paper proposes a GPU-accelerated outlier detection algorithm for continuous data streams using kernel density estimation approach. Experiments show that the proposed SOD_GPU algorithm is efficient for detecting outliers in high-dimensional, high-speed data streams, and produces results in a timely manner without compromising the outlier detection accuracy. The proposed method achieved up to 20X speedup compared to a respective multi-core CPU implementation, and the speedup increases with the number of data attributes and the input data rate.

This paper describes the design and the architecture of symbiote coprocessor unit (SCU)—a programmable streaming coprocessor for a heterogeneous reconfigurable logic-assisted data stream management systems (DSMSs) such as symbiote. The SCU is intended for streaming applications with real-time event and data processing that have stricter deadlines, high-bandwidth, and high-accuracy requirements. To meet these requirements, the SCU exploits unique characteristics of DSMSs, such as single-pass tuple processing, windowed operators, and inherent data level parallelism, using a single-instruction multiple-data very large instruction word (SIMD-VLIW) microarchitecture and a novel inverted distributed register file. In order to better explain the instruction set, design, and functionality of the various units in the SCU, this paper also provides a brief overview of SymQL—a procedural query language that we developed to describe the queries that can be executed on the SCU. Finally, this paper presents the performance of SCU using four queries that represent common data stream processing use-cases, one of them being similar to a query found in the Linear Road Benchmark. Using these queries on SCU simulation, we show that the SCU outperforms a software-only DSMS running on an AMD Opteron 2350 quad-core processor by 1.5–42 times.

Recommendation systems are a popular marketing strategy for online service providers. These systems predict a customer's future preferences from the past behaviors of that customer and the other customers. Most of the popular online stores process millions of transactions per day; therefore, providing quick and quality recommendations using the large amount of data collected from past transactions can be challenging. Parallel processing power of GPUs can be used to accelerate the recommendation process. However, the amount of memory available on a GPU card is limited; thus, a number of passes may be required to completely process a large-scale dataset. This paper proposes two parallel, item-based recommendation algorithms implemented using the CUDA platform. Considering the high sparsity of the user-item data, we utilize two compression techniques to reduce the required number of passes and increase the speedup. The experimental results on synthetic and real-world datasets show that our algorithms outperform the respective CPU implementations and also the naïve GPU implementation which does not use compression.

In this article, a brand new method of determining deadlock is presented. Most previous deadlock detection methods are algorithmic in the sense that they usually leverage some forms of Resource Allocation Graph (RAG) representations and then algorithms are devised to manipulate such representations in order to detect deadlock using information contained in the graph. Different from all previous methods, the proposed method actualizes the RAG with a digital circuit and uses it as a token-transmitting network. By supplying special input signals (tokens) to the network and observing the output tokens from the network, it is easier to identify which process nodes are reachable from each resource node in the graph. Using the reachability information, deadlock can be detected immediately. The time required to obtain the reachability information is determined by how fast the combinational circuit operates. Compared with previous algorithmic methods, the proposed deadlock detection can be deemed instant. We show that the proposed method is an order of magnitude faster than the previous fastest hardware mechanism and several orders of magnitude faster than traditional software-based algorithms.

The storage model of column-oriented databases is similar in structure to densely packed matrices/vectors found in many high-performance computing applications. Hence, hardware-accelerated vectorized matrix operations using Reconfigurable Logic (RL) coprocessors may find parallels in hardware acceleration of databases. In this article, we explore this hypothesis by proposing a multicontext, coarse-grained Reconfigurable coprocessor Unit (RU) model that is used to accelerate some of the database operations in hardware for column-oriented databases. We then describe the implementation of hardware algorithms for the equi-join, nonequi-join, and inverse-lookup database operations. Finally, we evaluate these algorithms using a microbenchmark query. Our results indicate that the query execution on the proposed RU model is one to two orders of magnitude faster than the software-only query execution.

Numerous monitoring applications such as traffic control systems, border patrol monitoring, and person locater services generate a large number of multimedia data streams that need to be analyzed and processed using image processing and data stream management techniques in order to detect significant events of interest or abnormal conditions. Such multimedia monitoring systems usually have high-bandwidth characteristics, stricter real-time deadlines, and high accuracy requirements. In an attempt to meet all of these requirements, we have designed Symbiote - a distributed Reconfigurable Logic Assisted multimedia Data Stream Management System (RLADSMS) at Indiana University Purdue University, Indianapolis (IUPUI) that provides hardware accelerated data stream processing using Field Programmable Gate Arrays (FPGAs).

Due to rapid technology advance, multiprocessor system-on-chips (MPSoCs) are likely to become commodity computing platforms for embedded applications. In the future, it is possible that an MPSoC is equipped with a large number of processing elements as well as on-chip resources. The management of these faces many challenges, among which deadlock is one of the most crucial issues. This paper presents a novel hardware-oriented deadlock detection algorithm suitable for current and future MPSoCs. Unlike previously published methods whose runtime complexities are often affected by the number of processing elements and resources in the system, the proposed algorithm leverages specialized hardware to guarantee O(1) overall runtime complexity. Such complexity is achieved by: 1) classifying resource allocation events; 2) for each type of events, using hardware to perform a set of specific detection and/or preparation operations that only takes constant runtime; and 3) updating necessary information for multiple resources in parallel in hardware. We implement the algorithm in Verilog HDL and demonstrate through simulation that each algorithm invocation takes at most four clock cycles.

Column-oriented databases are reported to perform orders of mag-nitude faster than traditional row-oriented databases for Decision Support System (DSS) workloads. However, there have been few investigations on the detailed hardware characterization of DSS benchmarks namely TPC-H for column-oriented databases. In this paper, we characterize the performance of the TPC-H benchmark for a popular column-oriented database called MonetDB running on a dual-core AMD Athlon machine. Specifically, we measure the performance of key microarchitectural components and provide very detailed analysis of the execution time breakdown of Mon-etDB during the execution of TPC-H queries. We analyze in detail the nature of the various stalls namely cache stalls, branch mis-prediction stalls and resource stalls in order to identify the causes of these performance impediments in column-oriented databases. We then indicate possible research directions to minimize these stalls in column-oriented databases. Finally, we compare our re-sults with published results on the characterization of TPC-H for row-oriented databases. As opposed to the previous approaches that used system-level monitoring, we used thread-level monitor-ing of database threads to study the performance of the database alone in isolation from the rest of the system. This enabled us to characterize the performance of databases independent of any other executing processes. 1.

This article describes a novel parallel multi-unit resource deadlock detection algorithm (MDDA) and its hardware implementation (MDDU). The contributions are (i) the first O(1) hardware deadlock detection, (ii) reduced O(min(m, n)) preparation, where m and n are the number of processes and resources, respectively, and (iii) support for multi-unit resources. O(min(m, n)), previously O(mtimesn), is achieved by performing all the searches for sink nodes for each and every resource in parallel in hardware over two matrices representing resource allocations as well as other auxiliary matrices. MDDU provides a fast and deterministic deadlock detection mechanism for multiprocessor system-on-chips (MPSoCs), which we predict will become prevalent in the near future in system designs. Our experiments demonstrate that MDDU always takes two clock cycles to detect deadlock regardless the size of the system. Lastly, the MPSoC area overhead due to MDDU is small, approximately 0.024 percent for MDDU16 x 16 on our example MPSoC.

This paper introduces a novel O(1) parallel deadlock detection approach for multi-unit resource system-on-a-chips (SoCs), inspired by Kimpsilas method in O(1) detection as well as Shiupsilas method in parallel processing. Our contributions are (i) the first O(1) hardware deadlock detection and (ii) O(min(m, n)) preparation, both for multi-unit resource systems, where m and n are the number of processes and resources, respectively. O(min(m, n)), previously O(m times n), is achieved by performing all the searches for sink nodes for each and every resource in parallel in hardware over a matrix representing resource allocations as well as other auxiliary matrices. Our experiments demonstrate that deadlock detection always takes two clock cycles.

In the future, high performance computing systems may consist of multiple multicore processors and reconfigurable logic coprocessors. Industry trends indicate that such coprocessors will be socket compatible to microprocessors and will be integrated on existing multiprocessor motherboards without any glue logic. Due to these trends, it is likely that such hybrid computing machines will be a breakthrough for various High Performance Computing (HPC) applications. It is essential to investigate the computer architecture of such hybrid computing machines that utilize reconfigurable logic coprocessors as application accelerators in a HPC system. Simulation can be used to aid this architectural research and guide design space exploration. In this paper, we first present a representative architecture for future hybrid computing machines. Next we present a survey of existing simulators and simulation methodologies for simulation of components of hybrid computing systems. FInally, we present some of the challenges and recommendations to encourage research in hybrid computing machines and their simulators.

This article proposes a novel O(n) Parallel Banker's Algorithm (PBA), which is a parallelized version of the Banker's Algorithm (BA), a well-known O(m\times n) deadlock avoidance algorithm. We implement the approach in hardware, which we call PBA Unit (PBAU). PBAU is not a mere Verilog HDL translation of BA, but a novel, fully hardware-oriented implementation exploiting maximum hardware parallelism of all computations in BA, resulting in O(1) runtime complexity in the best case and O(n) in the worst. PBAU is an Intellectual Property (IP) block that provides a mechanism of very fast, automatic deadlock avoidance for Multiprocessor System-on-a-Chip (MPSoC), which we predict will be the mainstream of future high performance computing environments. Furthermore, our PBAU supports multiple instance multiple resource systems. We demonstrate that PBAU not only avoids deadlock in a few clock cycles (several orders of magnitude faster than BA in software), but also achieves, in a particular example, a 19 percent speedup of application execution time over avoiding deadlock in software. Lastly, the MPSoC area overhead due to PBAU is small, less than 0.05 percent in our candidate MPSoC example.

This paper proposes a novel O(n) Parallel Banker's Algorithm (PBA) with a best-case run-time of O(1), reduced from an O(mn2) run-time complexity of the original Banker's Algorithm. We implemented the approach in hardware, which we call PBA Unit (PBAU), using Verilog HDL and verified the run-time complexity. PBAU is an Intellectual Property (IP) block that provides a mechanism of very fast, automatic deadlock avoidance for a MultiProcessor System-on-a-Chip (MPSoC, which we predict will be the mainstream of future high performance computing environments). Moreover, our PBA supports multiple-instance multiple resource systems. We demonstrate that PBAU not only avoids deadlock in a few clock cycles (1600X faster than the Banker's Algorithm in software) but also achieves in a particular example a 19% speedup of application execution time over avoiding deadlock in software. Lastly, the MPSoC area overhead due to PBAU is small, under 0.05% in our candidate MPSoC example.

This article presents a novel Parallel Deadlock Detection Algorithm (PDDA) and its hardware implementation, Deadlock Detection Unit (DDU). PDDA uses simple Boolean representations of request, grant, and no activity so that the hardware implementation of PDDA becomes easier and operates faster. We prove the correctness of PDDA and that the DDU has a runtime complexity of O ( min ( m , n )), where m is the number of resources and n is the number of processes. The DDU reduces deadlock detection time by 99%, (i.e., 100X) or more compared to software implementations of deadlock detection algorithms. An experiment involving a practical situation with an early deadlock condition showed that the time measured from application initialization to deadlock detection was reduced by 46% by employing the DDU as compared to detecting deadlock in software.

In this paper, we show the performance comparison and analysis result among three RTOSes: the Real-Time Unit (RTU) hardware RTOS, the pure software Atalanta RTOS and a hardware/software RTOS composed of part of Atalanta interfaced to the System-on-a-Chip Lock Cache (SoCLC) hardware. We also present our RTOS configuration framework that can automatically configure these three RTOSes. The average-case simulation result of a database application example on a three-processor system running thirty tasks with RTU and the same system with SoCLC showed 36% and 19% overall speedups, respectively, as compared to the pure software RTOS system.

Intertask/interprocess synchronization overheads may be significant in a multiprocessor-shared memory System-on-a-Chip implementation. These overheads are observed in terms of lock latency, lock delay and memory bandwidth consumption in the system. It has been shown that a hardware solution brings a much better performance improvement than the synchronization algorithms developed in software [3]. Our previous work presented a SoC Lock Cache (SoCLC) hardware mechanism which resolves the Critical Section (CS) interactions among multiple processors and improves the performance criteria in terms of lock latency, lock delay and bandwidth consumption in a shared memory multi-processor SoC for short CSes [1]. This paper extends our previous work to support long CSes as well. This combined support involves modifications both in the RTOS kernel level facilities (such as support for preemptive versus non-preemptive synchronization, interrupt handling and RTOS initialization) and in the hardware mechanism. The worst-case simulation results of a database application model with client-server pair of tasks on a four-processor system showed that our mechanism achieved a 57% improvement in lock latency, 14% speed up in lock delay and a 35% overall speedup in total execution time.