High-throughput label-free single cell screening technology has been studied for noninvasive analysis of various kinds of cells. We tackle the cell identification task in the cell sorting system as a continuous skyline computation. Skyline Computation is a method for extracting interesting entries from a large population with multiple attributes. Jointed rooted-tree (JR-tree) is continuous skyline computation algorithm that manages entries using a rooted-tree structure. JR-tree delays extend the tree to deeper levels to accelerate tree construction and traversal. In this study, we proposed the JR-tree-based parallel skyline computation accelerator. We implemented it on a field-programmable gate array (FPGA). We evaluated our proposed software and hardware algorithms against an existing software algorithm using synthetic and real-world datasets.

Skyline Computation is a method for extracting interesting entries from a large population with multiple attributes. These entries, called skyline or Pareto optimal entries, are known to have extreme characteristics that cannot be found by using outlier detection methods. Skyline computation is an important task for characterizing large amounts of data and selecting interesting entries with extreme features. When the population changes dynamically, the task of calculating a sequence of skyline sets is called a continuous skyline computation. This task is known to be difficult for the following reasons: (1) information must be kept for non-skyline entries, since they may join the skyline in the future; (2) the appearance or disappearance of even a single entry can change the skyline drastically; and (3) it is difficult to adopt a geometric acceleration algorithm for skyline computation tasks with high-dimensional datasets. A new algorithm, called jointed rooted-tree (JR-tree), has been developed that manages entries using a rooted-tree structure. JR-tree delays extend the tree to deeper levels to accelerate tree construction and traversal. In this study, we propose the JR-tree based continuous skyline computation acceleration algorithm. Our hardware algorithm parallelizes the calculations of dominance relation between a target entry and the skyline entries. We implemented our hardware algorithm on an FPGA and showed that high-speed tree construction and traversal can be realized. Comparing our FPGA-based implementation with an Intel CPU running state-of-the-art software algorithms, it was found to reduce the query processing time for synthetic and real-world datasets. Our hardware implementation is 1.7x to 35x faster than the software implementations.

High-throughput label-free single cell screening technology has been studied for noninvasive analysis of various kinds of cells. Selecting the prominent cells with extreme features from a large number of cells is an important and interesting problem. We call this problem the serendipitous searching problem (SSP), where it is important to find entries located near the rind of the population in multi-dimensional feature space. We tackle the SSP as a continuous skyline computation. The skyline computation is originally used to extract interesting entries from a database with multi-attributions. The skyline points are continuously updated at the time existing entries disappear and new entries arrive. In this paper, we propose a balanced jointed rooted tree (BJR-tree) algorithm and a nondominated relation cache (ND-cache) for continuous skyline computation. The BJR-tree expresses the dominance relation as an arc and stores the "dominated" relations. The ND-cache complements the BJR-tree by reducing the recalculation of the dominance relations. The execution times of the BJR-tree and existing continuous skyline computation algorithms are compared on randomly constructed synthetic datasets with multiple temporal and spatial features. The BJR-tree is then evaluated on actual measured information of blood cells. On the two and eight-dimensional synthetic datasets, the BJR-tree computed the continuous skylines approximately 3x and 70x faster than the LookOut, respectively. On actual datasets, the BJR-tree is approximately 2.4x faster than the LookOut.

Non-uniform arrangement of on-chip resources could outperform the uniform design. The way of arrangement itself, however, has not been well researched yet. In this research, we proposed an automatic method for better arrangement of the on-chip resources using GA.

The skyline operator has been proposed as a method for extracting highly-utility samples from a large database. A set of the extracted samples is called `skyline'. The theme of the MEMOCODE 2015 Design Contest is to accelerate continuous skyline computation, skyline computing for a streaming dataset, on any platform. In this paper, we present our method that achieved the best performance in the contest. We describe our data structure, algorithms, and optimization methods for the contest reference code in the multi-core processor. We have accelerated our solution in the two aspects of efficient algorithms and code optimizations. The task of the contest is to compute the skyline at each time-step for 800,000 entries with a seven-dimensional vector value and the activation time and the deactivation time. We use one commodity computer and the average runtime of our solution is 407 milliseconds.

Directory is one of the common method to maintain cache coherence in multi/many-core systems. However, directory has problems in area, latency and complexity of protocol. Conversely, directoryless coherence mechanism, where each core invalidates its own L1 cache block (tear-off copy) is proposed. The problem of this method is that the cache blocks which are not written by another core are invalidated. We accelerate the coherence mechanism by speculatively executing with the value of these invalidated cache blocks. Our results show 2\% acceleration on average over derectory based MOESI protocol in 16 core system.

Data prefetching, advanced cache replacement policy, and memory access scheduling are incorporated in modern processors. Typically, each technique holds recently accessed locations independently and controls the memory subsystem based on the prediction of future memory access. Unfortunately, these specific optimizations often increase the implementation cost, decrease the system performance, and reduce scalability of the processor chip.

A novel data prefetching method -- access map pattern matching (AMPM) -- that uses "memory access map" is proposed. The AMPM prefetching concentrate hardware resources on collecting the access footprint of the frequently accessed area which we called "hot zones". 2-bit state is associated with each cache lines of hot zone. A set of these states is called "memory access map". Prefetch requests are generated from the pattern matching of the memory access map. The pattern matching detects multiple memory access patterns in parallel and generates more prefetch requests than conventional prefetchers. The evaluation result shows that the AMPM prefetcher improves performance by 42.0% in FP benchmarks.

Massively parallel machines that integrate a large number of simple processors and small scratch-pad memories (SPMs) into a single chip can achieve a high peak performance per watt of power. In these machines, communication optimizations are important because the communication bandwidth tends to be a bottleneck. Previously proposed communication optimizations using copy candidates, which have been shown to be effective, detect frequently reused array regions by compile-time analysis and copy the regions to scratch-pad memories nearer to the processors. However, they have been proposed for uniprocessor systems or small parallel machines with one or more layers of scratch-pad memories, and the analysis time increases when they are applied to massively parallel machines. In this paper, we propose Multilayer Copy-candidate Analysis for Massively Parallel machines (MCAMP), a communication optimization method for massively parallel machines. MCAMP re-formalizes the framework used in earlier works and improves the scalability of the analysis by assuming the homogeneity of the target systems. We implemented an MCAMP optimizer, which takes an input program that consists of perfectly nested loops containing array references and computation codes, and generates optimized communication. We measured the performance of the output programs of the MCAMP optimizer by executing them on a real massively parallel machine GRAPE-DR using a software tool chain that we also implemented. We showed that MCAMP can achieve optimal data transfer patterns and comparable performance to that of hand-optimized codes with a short analysis time.

Model-based verification is extensively begin used for accelerating the development of embedded system. However, by this approach, a model and actual RTL are required to be implemented separately, which increases the time required to ensure the equivalence of virtual models and actual hardware. To reduce the costs incurred in separate implementations, we propose to directly generate RTL from verification model used in CoMET, which is a callback-based verification environment. We design and implement CVC, a compiler used for generating RTL, using a callback-based verification model described in a subset of the C language; we impose a restriction on CVC to describe the callback efficiently. Our method enables developers to implement the complete RTL without any compromises in the RTL performance just after the verification of the callback-based model is completed.

With the rapid progress of high-performance cluster applications, data transfer between clusters in distant locations becomes more important. But, it is difficult to transfer data using parallel TCP streams on long distance high bandwidth network. In this paper, we microscopically observe parallel TCP streams on 10 Gbps network using our network analyzer, propose, implement, and evaluate "Stream Equalizer'' which relaxes self-congestion and balances throughput among streams.We evaluate it using a real wide-area network over the Pacific Ocean.The network analyzer and the Stream Equalizer are implemented on FPGA-based programmable high-speed network testbed TGNLE-1.

End-to-end communications on 10 Gigabit Ethernet (10 GbE) WAN became popular. However, there are difficulties that need to be solved before utilizing Long Fat-pipe Networks (LFNs) by using TCP. We observed that the followings caused performance depression: short-term bursty data transfer, mismatch between TCP and hardware support, and excess CPU load. In this research, we have established systematic methodologies to optimize TCP on LFNs. In order to pinpoint causes of performance depression, we analyzed real networks precisely by using our hardware-based wire-rate analyzer with 100-ns time-resolution. We took the following actions on the basis of the observations: (1) utilizing hardware-based pacing to avoid unnecessary packet losses due to collisions at bottlenecks, (2) modifying TCP to adapt packet coalescing mechanism, (3) modifying programs to reduce memory copies. We have achieved a constant through-put of 9.08 Gbps on a 500 ms RTT network for 5 h. Our approach has overcome the difficulties on single-end 10 GbE LFNs.

In modern processors it is difficult to implement a high speed and area effective fault-tolerant execution stage that can tolerate defects and hard faults. The structure of Functional Units (FU) is complicated, unlike registers or cache memory. Conventional approaches are able to tolerate faults but overhead is large. We propose Heterogeneous Functional Units (HFUs), with high speed and area effective fault-tolerant execution stages by using a combination of fast FUs and fault-tolerant FUs. Simulation results from SPEC2000 benchmarks show that HFUs have 99%(HFU-Det), 94.2%(HFU-1) of relative IPC for a simple duplication of fast FUs. HFU is faster than the simple duplication of fault-tolerant FUs, that have 84.0%.

We describe the GRAPE-DR (Greatly Reduced Array of Processor Elements with Data Reduction) system, which will consist of 4096 processor chips each with 512 cores operating at the clock frequency of 500 MHz. The peak speed of a processor chip is 512Gflops (single precision) or 256 Gflops (double precision).

Many excepting instructions cannot be removed by existing partial redundancy elimination (PRE) algorithms because the ordering constraints must be preserved between the excepting instructions, which we call exception dependencies. In this work, we propose Sentinel PRE, a PRE algorithm that overcomes exception dependencies and retains program semantics. Sentinel PRE first hoists excepting instructions without considering exception dependencies, and then detects exception reordering by fast analysis. If an exception occurs at a reordered instruction, it deoptimizes the code into the one before hoisting. Since we rarely encounter exceptions in real programs, the optimized code is executed in almost all cases. We implemented Sentinel PRE in a Java just-in-time compiler and conducted experiments. The results show 9.0% performance improvement in the LU program in the Java Grande Forum Benchmark Suite.

In this paper, we propose methods to enable high-speed and memory efficient TCP stream level string matching using FPGA. Packet loss and inconsistent retransmissions are handled without dropping packets. Received packets are processed in their arriving order to reduce the buffering memory size. Consistency of retransmission packets is checked using hash value comparison. We evaluate the proposed system using Xilinx XC2VP100-5 FPGA. A 40Gbps network is supported by the proposed system with 140MB memory usage under a realistic traffic pattern. In addition, the proposed system realizes 39.3Gbps packet-processing throughput for a 1017 characters rule, and 1.85Gbps throughput for a 16375 characters rule.

We propose a novel replacement algorithm, called Inter-Reference Gap Distribution Replacement (IGDR), for set-associative secondary caches of processors. IGDR attaches a weight to each memory-block, and on a replacement request it selects the memory-block with the smallest weight for eviction. The time difference between successive references of a memory-block is called its Inter-Reference Gap (IRG). IGDR estimates the ideal weight of a memory-block by using the reciprocal of its IRG.To estimate this reciprocal, it is assumed that each memory-block has its own probability distribution of IRGs; from which IGDR calculates the expected value of the reciprocal of the IRG to use as the weight of the memory-block. For implementation, IGDR does not have the probability distribution; instead it records the IRG distribution statistics at run-time. IGDR classifies memory-blocks and records statistics for each class. It is shown that the IRG distributions of memory-blocks correlate their reference counts, this enables classifying memory-blocks by their reference counts. IGDR is evaluated through an execution-driven simulation. For ten of the SPEC CPU2000 programs, IGDR achieves up to 46.1% (on average 19.8%) miss reduction and up to 48.9% (on average 12.9%) speedup, over the LRU algorithm.

As the network speed grows, inter-layer coordination becomes more important. This paper shows 3 inter-layer coordination methods; (1) "Comet-TCP"; cooperation of data-link layer and transport layer using hardware, (2) "Transmission Rate Controlled TCP (TRC-TCP)"; cooperation of data-link layer and transport layer using software, and (3) "Dulling Edges of Cooperative Parallel streams (DECP)"; cooperation of transport layer and application layer. We show the experimental results of file transfer at Bandwidth Challenge in SC2003; one and a half round trip from Japan to U.S., 15,000 miles, which has 350 ms RTT and 8.2 Gbps bandwidth. Comet-TCP hardware solution attained max 7.56 Gbps using a pair of 16 IA servers, which is 92% of available bandwidth and DECP software attained max 7.01 Gbps using a pair of 32 IA servers.

The importance of highly fault-tolerant computing systems has widely been recognized. We propose an FPGA architecture with a degrading strategy to increase fault-tolerance in a CPU. Previously, duplication and substitution methods have been proposed, but former methods waste redundant circuits and later methods increase computing speed as faults occur. We propose a reconstitution method with FPGA technology. Using our method, execution speed of the CPU gradually decreases as permanent faults occur. The CPU consists of functional blocks (FB), that is re-configurable logic blocks. When a fault occurs, the broken FB is discarded. As the number of valid FB decreases, function units of it is scaled down, therefore, execution time increases. In our simulation, speed degradation is less than 100% when 70% of whole FBs are broken. Compared with previous methods, speed degradation is smaller in case that many permanent faults occur.

We propose data sharing facility for data intensive scientific research, "Data Reservoir"; which is optimized to transfer huge amount of data files between distant places fully Utilizing multi-gigabit backbone network. In addition, "Data Reservoir" can be used as an ordinary UNIX server in local network without any modification of server softwares. We use low-level protocol and hierarchical striping to realize (1) separation of bulk data transfer and local accesses by cashing, (2) file-system transparency, I.e. interoperable whatever in higher layer than disk driver, including file system. (3) scalability for network and storage. This paper shows our design, implementation using iSCSI protocol [1] and their performances for both 1Gbps model in the real network and 10Gbps model in our laboratory.

The experimental results clearly show that the performance of ADSM scheme is limited by the communication of unnecessary data, while that of the UDSM scheme is limited by the instrumentation overhead. The UDSM scheme reduces transmission of unnecessary data and automatically prevents the severe false sharing at fetch-on-write, which is the problem in the page-based scheme.

On a large scale parallel computer system, shared memory provides a general and convenient programming environment. The paper describes a lightweight method for constructing an efficient shared memory system supported by hierarchical coherence management and generalized combining. The hierarchical management technique and generalized combining cooperate with each other. We eliminate the following heavyweight and high cost factors: a large amount of directory memory which is proportional to the number of processors, a separate memory component for the directory, tag/state information, and a protocol processor. In our method, the amount of memory required for the directory is proportional to the logarithm of the number of processors. This implies that a single word for each memory block is sufficient for covering a massively parallel system and that the access costs of the directory are small. Moreover, our combining technique, generalized combining, does not expect the accidental events which existing combining networks do, that is, events that messages meet each other at a switching node. A switching node can combine succeeding messages with a preceding one even after the preceding message leaves the node. This can increase the rate of successful combining. We have developed a prototype parallel computer OCHANOMIZ-5, that implements this lightweight distributed shared memory and generalized combining with simple hardware. The results of evaluating the prototype's performance using several programs show that our methodology provides the advantages of parallelization.

To execute a shared memory program efficiently, we have to manage memory consistency with low overheads, and have to utilize communication bandwidth of the platform as much as possible. A software distributed shared memory (DSM) can solve these problems via proper support by an optimizing compiler. The optimizing compiler can detect shared write operations, using interprocedural points-to analysis. It also coalesces shared write commitments onto contiguous regions, and removes redundant write commitments, using interprocedural redundancy elimination. A page based target software DSM system can utilize communication bandwidth, owing to coalescing optimization. We have implemented the above optimizing compiler and a run time software DSM on AP1000+. We have obtained a high speed-up ratio with the SPLASH-2 benchmark suite. The result shows that using an optimizing compiler to assist a software DSM is a promising approach to obtain a good performance. It also shows that the appropriate protocol selection at a write commitment is an effective optimization.

Article Free Access Share on Speculative execution model with duplication Authors: Kei Hiraki Department of Information Science, University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-0033 Japan Department of Information Science, University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-0033 JapanView Profile , Junji Tamatsukuri Department of Information Science, University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-0033 Japan Department of Information Science, University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-0033 JapanView Profile , Takashi Matsumoto Department of Information Science, University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-0033 Japan Department of Information Science, University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-0033 JapanView Profile Authors Info & Claims ICS '98: Proceedings of the 12th international conference on SupercomputingJuly 1998 Pages 321–328https://doi.org/10.1145/277830.277907Online:13 July 1998Publication History 5citation337DownloadsMetricsTotal Citations5Total Downloads337Last 12 Months3Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We introduce a novel high-speed user-level communication and synchronization scheme "Memory-Based Communication Facilities (MBCF)" for a general-purpose system with an off-the-shelf communication-hardware.This mechanism is protected and virtualized as completely as memory so that it can be used not only in parallel systems but also in distributed systems.The MBCF realizes the direct remotememory-accesses in user-task-spaces and offers programmers and compilers a wide variety of functions and a large sharedmemory space.In this paper we first explain outlines and features of the MBCF, and present the high-speed implementation techniques for the MBCF.Then this paper describes varieties of the MBCF functions and introduces two novel memory-based mechanism: the Memory-Based FIFO and the Memory-Based Signal.Next we show that the MBCF is more flexible and less expensive than the messagepassing-style system-interfaces for communication or generalized active messages.Finally we show performance evaluations on the real MBCF implementation using lOOBASE-TX Ethernet.

Article Free Access Share on An I/O network architecture of the distributed shared-memory massively parallel computer JUMP-1 Authors: Hironori Nakajo Department of Computer and Systems Engineering, Kobe University Department of Computer and Systems Engineering, Kobe UniversityView Profile , Satoshi Ohtani Department of Computer and Systems Engineering, Kobe University Department of Computer and Systems Engineering, Kobe UniversityView Profile , Takashi Matsumoto Department of Information Science, The University of Tokyo Department of Information Science, The University of TokyoView Profile , Masadi Kohata Department of Information and Computer Engineering, Okayama University of Science Department of Information and Computer Engineering, Okayama University of ScienceView Profile , Kei Hiraki Department of Information Science, The University of Tokyo Department of Information Science, The University of TokyoView Profile , Yukio Kaneda Department of Computer and Systems Engineering, Kobe University Department of Computer and Systems Engineering, Kobe UniversityView Profile Authors Info & Claims ICS '97: Proceedings of the 11th international conference on SupercomputingJuly 1997 Pages 253–260https://doi.org/10.1145/263580.263645Published:11 July 1997Publication History 4citation247DownloadsMetricsTotal Citations4Total Downloads247Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Latency associated with memory accesses and process communications are one of the most difficult obstacles in constructing a practical massively parallel system. So far, two approaches to hide latencies have been proposed. They are prefetching and multi-threading. An instruction-level data-driven computer is an ideal test-bed for evaluating these latency hiding methods because prefetching and multi-threading are naturally implemented in an instruction-level data-driven computer as unfolding and concurrent execution of multiple contexts. This paper evaluates latency hiding methods on SIGMA-1, a dataflow supercomputer developed in Electrotechnical Laboratory. As a result of evaluation, these methods are effective to hide static latencies but not effective to hide dynamic latencies. Also, concurrent execution of multiple contexts is more effective than prefetching.

In multiprocessor systems, overheads caused by interprocessor communication and synchronization have been one of the largest obstacles for efficient execution of parallel programs. To reduce these overheads in shared-memory/shared-bus multiprocessors, we have proposed two hardware mechanisms: the Inter-Cache Snoop Control Mechanism (ICSCM), which dynamically switches snoop-protocols for improving shared-bus utilization, and the Mechanism for Integrated Synchronization and Communication (MISC), which extends ICSCM to support producer-consumer type synchronization efficiently. We have developed an execution-driven multiprocessor simulator for evaluating performance with these mechanisms. Simulation experiments on doacross loops show remarkable speed-ups by ICSCM/MISC mechanisms. Although the proposed mechanisms are originally implemented on a single shared-bus system, they are easily applicable to a clustered multiprocessing systems. The methods used in a clustered system are discussed.

In the past, various computer languages aimed at users of dataflow computers have been designed and implemented.VAL, Id and SISAL are famous examples.One concept that is common to such languages is to maintain a sense of functionality by introducing a single assignment rule for all variables.DFCII, Dataflow C II, the language proposed here, is designed for writing practical application programs and system programs that must be executed in parallel on the SIGMA-1.It is the most important dataflow research

This paper describes the research activity on dataflow computing in Japan focusing on dataflow computer development at the Electrotechnical Laboratory (ETL). First, the history of dataflow computer development in Japan is outlined. Some distinguished milestones in the history are mentioned in detail. Second, two types of dataflow computing systems developed at ETL, SIGMA-1 and EM-4, are described with their research goals. The fundamental characteristics of the both systems are given and some comparisons are made. Finally, future problems toward new generation computer systems to meet the challenge of Tera FLOPS machines are discussed.

A highly parallel (more than a thousand) dataflow machine EM-4 is now under development. The EM-4 design principle is to construct a high performance computer using a compact architecture by overcoming several defects of dataflow machines. Constructing the EM-4, it is essential to fabricate a processing element (PE) on a single chip for reducing operation speed, system size, design complexity and cost. In the EM-4, the PE , called EMC-R, has been specially designed using a 50,000-gate gate array chip. This paper focuses on an architecture of the EMC-R. The distinctive features of it are: a strongly connected arc dataflow model; a direct matching scheme; a RISC-based design; a deadlock-free on-chip packet switch; and an integration of a packet-based circular pipeline and a register-based advanced control pipeline. These features are intensively examined, and the instruction set architecture and the configuration architecture which exploit them are described.

Structure-flow processing is proposed as a novel scheme for handling data structures such as vectors in data-flow architecture. The main objective of structure-flow processing is to enhance the vector processing performance. In this scheme, the arrival of a data structure unrolls the control structure that processes the data structure itself. A high-level structure is an implementation mechanism of a structure-flow scheme on a practical data-flow computer. Since all the computation is executed by instruction-level data-flow architecture, scalar-level parallelism and function-level parallelism are also fully utilized by this scheme. The SIGMA-1 architecture that supports high-level structure processing is discussed. Performance measurements show that vector programs can be executed three to four times faster than by unfolding using scalar dataflow processing.>

A processing element and a structure element of data flow computer SIGMA-1 for scientific computations is now operational. The elements are evaluated for several benchmark programs. For efficient execution of loop constructs, the sticky token mechanism which holds loop invariants is evaluated and exhibits a remarkable effect. From the standpoint that performance of a single processor of a data flow computer must be comparable to that of a Von Neumann computer, comparison of both computers is discussed and improvement of the SIGMA-1 instruction set is proposed.

Two parallel hashing algorithms based on open and chained hashing are discussed. The parallel chained hashing algorithm is efficient even in the environment where deletion and insertion frequently occur. The chained hashing memory with fewer memory banks has a performance equivalent to that of the open hashing memory.

Functional aspects of a machine called FLATS are described. FLATS aims to efficiently run both numerical and algebraic programs. Overflow free and variable precision arithmetic, table look-up computation, and associative computation based on single-hit content addressed tables are introduced for advanced numerical, algebraic and symbolic computing. Hashing hardware, tag mechanism and hardware list processing are used to realize these features.