Heapsort algorithm was found many decades ago, but no parallel heapsort algorithm had been presented. In our previous work, we challenged the development of a parallel heapsort algorithm. In this paper we improve our previous algorithm partially and analyze the performance in detail. As a more massive amount of data are sorted, or as more complex comparison is required for sorting, our parallel heapsort algorithm can sort the data more efficiently.

Thread-Level Speculation (TLS) is an approach to enhance the opportunity of parallelization by executing tasks in parallel based on the assumption that the task has no dependencies on any earlier task in program order. But if any dependency is detected during the execution, the task should be aborted and re-executed. So the frequency of aborts is one of the factors that damage the performance of the speculative execution. In this paper we propose the “code shelving” scheme to avoid aborts or eliminate the penalty of the abort. We have implemented it on our TLS system, which is named Speculative Memory (SM), and investigated its performance characteristics. Our evaluation results reveal the code shelving can significantly improve the performance of pure speculation that does not use the code shelving.

This paper improves the parallel multi-dimensional indexing system which stores data into several multi-dimensional indexes and retrieves required data from them in parallel. This system treats a set of data as a rectangle, which covers the data. The rectangle is inserted into an index. We must consider two important points. One is that the area of each index covers as wide as possible so that many indexes could be used in the retrieval. The other is that the number of rectangles which each index has is the same as possible so that the time in finishing the retrieval on each index could be the same as possible. The conventional system selects an index to which a rectangle is moved by using the area that the index covers and the number of rectangles that the index has. The conventional system first evaluates the degree of the expansion of area and then evaluates the number of rectangles. This paper changes the evaluation order. The number of rectangles is firstly evaluated. It is experimentally shown that the new evaluation order gives us good retrieval performance.

We have proposed a distributed storage system which autonomously migrates a data block into a suitable storage node. In our storage system, heavily accessing data blocks will be migrated autonomously to a higher performance storage node (i.e. an upper storage tier), and rarely accessed data blocks will be migrated to a lower performance storage node (i.e. a lower storage tier). Our investigation shows that it may need several migrations in order to locate a data block onto the most suitable storage node when the destination storage tier has a lot of storage nodes. In this paper, we propose a method to enhance data migration efficiency to improve I/O performance of the whole system. Our simulation results show that the proposed method can greatly reduce I/O execution time than the previous one. The execution time was reduced about one-fifth at the maximum in a system with several hundred scale nodes.

Many techniques for parallelizing a sequentially coded program have been developed and put to practical use, but there are many cases in which program codes cannot be parallelized because it is impossible to assure that their parallel execution does not violate the data dependencies in the program. To parallelize such programs, we have previously proposed speculative memory (SM). With SM, programmers can specify the parallel and speculative execution of threads explicitly in their programs. The SM system manages the memory data that are speculatively read or written by the threads running in parallel. When the system detects inconsistent memory accesses, it recovers the computational state of the program and restarts the execution. If such inconsistencies are not encountered often, we can expect the total execution time of the program to be shorter. In this paper we present a software implementation of SM (SSM). We have developed an SM library by using POSIX threads. In spite of large overheads that are essentially unavoidable in a software implementation, our SSM system can shorten the execution time of a program that compilers cannot parallelize automatically.

Transactional memory (TM) is promising to make parallel programming easier. Many hardware implementations of transactional memory (HTM) have been proposed to improve the performance, but they still suffer from some overheads when a transaction either commits or aborts. So we have been developing a novel new HTM design, called Delayed-Committing TM (DCTM), which enables transactions of arbitrary size to commit or abort in a fixed number of cycles - typically, one. In this paper, we analyze the performance of our DCTM system in detail. Simulation results show that the performance of our DCTM system is as much as 35.7% better than the performance of a conventional HTM system, which has almost no overhead when a transaction aborts but detects conflict and publishes speculatively modified data when a transaction commits. Furthermore, we can expect to improve performance more by increasing the bandwidth of the common bus connecting processing nodes with each other.

We have proposed a distributed storage system which dynamically makes storage tiers and optimizes location of data blocks autonomously. This aims to enhance the I/O performance of the storage system without remarkable network overhead. Our system dynamically organizes storage tiers considering device characteristics. And the data blocks will be placed in a suitable storage tier according to their access pattern. In this paper, we propose a method to select the destination storage node for migration using an access characteristic of a data block to be migrated. This method ranks the storage nodes dynamically, and each storage node configures storage tiers autonomously. Simulation results show that our scheme can short the execution time of a program with file I/O by 49% at maximum, in comparison with the static migration without considering the access characteristics of the migration data.

We have been developing a multiprocessor architecture which executes iterations of a loop speculatively in parallel. In this paper, we present speculative memory (SM), in order to enable the large-scale speculation which supports the speculative execution of the iteration of arbitrary size and duration. With SM, a programmer can hint explicitly that iterations of a certain loop are preferable to be executed speculatively in parallel. SM manages multiple values (versions) of speculatively modified data. SM also features the memory renaming and the delayed execution of the program codes, which could be viewed as a dynamic code migration. These can remove the dependencies between loop iterations or alleviate the occurrence of dependency hazards. Thus, SM can improve the success rate of the speculation, and consequently, makes it possible to extract the thread-level parallelism more than ever before.

In our previous work, we had proposed a distributed storage system which aims to optimize the locations of data blocks on the basis of their access frequency. In order to relocate data blocks at an appropriate node, each node should collect fresh information about storage utilization of other nodes. However, frequent information exchange might become the cause of network congestion. In this paper, we propose a method to improve the storage information freshness and to suppress information exchange traffic. This method controls the propagation interval according to the condition of a storage node. We also show that Ethernet frames can be reduced by merging packets even if storage information is transferred at short intervals.

Mechanical stretch-induced tyrosine phosphorylation in the proline-rich 306-residue substrate domain (CasSD) of p130Cas (or BCAR1) has eluded an experimentally validated structural understanding. Cellular p130Cas tyrosine phosphorylation is shown to function in areas without internal actomyosin contractility, sensing force at the leading edge of cell migration. Circular dichroism shows CasSD is intrinsically disordered with dominant polyproline type II conformations. Strongly conserved in placental mammals, the proline-rich sequence exhibits a pseudo-repeat unit with variation hotspots 2-9 residues before substrate tyrosine residues. Atomic-force microscopy pulling experiments show CasSD requires minimal extension force and exhibits infrequent, random regions of weak stability. Proteolysis, light scattering and ultracentrifugation results show that a monomeric intrinsically disordered form persists for CasSD in solution with an expanded hydrodynamic radius. All-atom 3D conformer sampling with the TraDES package yields ensembles in agreement with experiment when coil-biased sampling is used, matching the experimental radius of gyration. Increasing β-sampling propensities increases the number of prolate conformers. Combining the results, we conclude that CasSD has no stable compact structure and is unlikely to efficiently autoinhibit phosphorylation. Taking into consideration the structural propensity of CasSD and the fact that it is known to bind to LIM domains, we propose a model of how CasSD and LIM domain family of transcription factor proteins may function together to regulate phosphorylation of CasSD and effect machanosensing.

Multiple instruction execution is a major approach to designing high-performance processors. Superscalar and VLIW processor that utilize instruction level parallelism are usually focused on. On the other hand, the multithreaded processor can be expected to achieve a high degree of multiple instruction execution by utilizing coarse grain parallelism. Many computer graphics applications (such as the radiosity method and ray-tracing method) can be optimized by reorganizing the code to take advantage of coarse grain parallelism, but the degree of instruction level parallelism is not sufficient for a superscalar processor. Experimental result using the radiosity method shows that the 4-thread multithreaded processor achieves 2.9 times speedup over single thread, while the 4-issue superscalar processor manages around 1.5 times. By duplicating two kinds of function units, the performance of a multithreaded processor increases to 3.7 times, but the performance of a superscalar processor is saturated at around 1.5 times. Therefore, for computer graphics applications, the multithreaded processor is a better approach than the superscalar processor.>

In this paper, we propose a multithreaded processor architecture which improves machine throughput. In our processor architecture, instructions from different threads (not a single thread) are issued simultaneously to multiple functional units, and these instructions can begin execution unless there are functional unit conflicts. This parallel execution scheme greatly improves the utilization of the functional unit. Simulation results show that by executing two and four threads in parallel on a nine-functional-unit processor, a 2.02 and a 3.72 times speed-up, respectively, can be achieved over a conventional RISC processor.Our architecture is also applicable to the efficient execution of a single loop. In order to control functional unit conflicts between loop iterations, we have developed a new static code scheduling technique. Another loop execution scheme, by using the multiple control flow mechanism of our architecture, makes it possible to parallelize loops which are difficult to parallelize in vector or VLIW machines.