Multi-/many-core processors are being increasingly used to reduce power consumption and improve performance. In addition, the use of Model-Based Development for embedded systems has been increasing. Relative to these trends, Model-Based Parallelizer (MBP) has an essential role in parallelizing applications (i.e., Simulink blocks) at the model level. MBP maps Simulink blocks to cores using various types of information such as block characteristics, a C code, and the multi-/many-core hardware implementation. However, MBP does not consider many-core hardware with cluster structures. This paper proposes an algorithm that decides on core allocations by considering cluster structures. The proposed algorithm combines two other algorithms: one algorithm uses the core allocation of MBP and path analysis at the cluster-level and considers the influence of communication contention to decide on cluster allocations, and the other algorithm uses the results of MBP and remaps cluster allocations. The proposed algorithm produces better results than its component algorithms could separately. Evaluations demonstrate that the proposed algorithm obtained the better results than the existing method in terms of execution time on random and real models.

The problem of scaling out relational join performance for large data sets in the database management system (DBMS) has been studied for years. Although in-memory DBMS engines can reduce load times by storing data in the main memory, join queries still remain computationally expensive. Modern graphics processing units (GPUs) provide massively parallel computing and may enhance the performance of such join queries; however, it is not clearyet in what condition relational joins perform well on GPUs. In this paper, we identify the performance characteristics of GPU computing for relational joins by implementing several well-known GPU-based join algorithms under various configurations. Experimental results indicate that the speedup ratio of GPU-based relational joins to CPU-based counterparts depends on the number of compute cores, the size of data sets, join conditions, and join algorithms. In the best case, the speedup ratios are up to 6.67 times for non-index joins, 9.41 times for sort index joins, and 2.55 times for hash joins. The execution time of GPU-based implementation for index joins, on the other hand, is only about 0.696 times less than the execution time of the CPU's counterparts.

Object detection is a fundamental challenge facing intelligent applications. Image processing is a promising approach to this end, but its computational cost is often a significant problem. This paper presents schemes for accelerating the deformable part models (DPM) on graphics processing units (GPUs). DPM is a well-known algorithm for image-based object detection, and it achieves high detection rates at the expense of computational cost. GPUs are massively parallel compute devices designed to accelerate data-parallel compute-intensive workload. According to an analysis of execution times, approximately 98 percent of DPM code exhibits loop processing, which means that DPM could be highly parallelized by GPUs. In this paper, we implement DPM on the GPU by exploiting multiple parallelization schemes. Results of an experimental evaluation of this GPU-accelerated DPM implementation demonstrate that the best scheme of GPU implementations using an NVIDIA GPU achieves a speed up of 8.6x over a naive CPU-based implementation.

Graphics processing units (GPUs) provide an order-of-magnitude improvement on peak performance and performance-per-watt as compared to traditional multicore CPUs. However, GPU-accelerated systems currently lack a generalized method of power and performance prediction, which prevents system designers from an ultimate goal of dynamic power and performance optimization. This is due to the fact that their power and performance characteristics are not well captured across architectures, and as a result, existing power and performance modeling approaches are only available for a limited range of particular GPUs. In this paper, we present power and performance characterization and modeling of GPU-accelerated systems across multiple generations of architectures. Characterization and modeling both play a vital role in optimization and prediction of GPU-accelerated systems. We quantify the impact of voltage and frequency scaling on each architecture with a particularly intriguing result that a cutting-edge Kepler-based GPU achieves energy saving of 75% by lowering GPU clocks in the best scenario, while Fermi- and Tesla-based GPUs achieve no greater than 40% and 13%, respectively. Considering these characteristics, we provide statistical power and performance modeling of GPU-accelerated systems simplified enough to be applicable for multiple generations of architectures. One of our findings is that even simplified statistical models are able to predict power and performance of cutting-edge GPUs within errors of 20% to 30% for any set of voltage and frequency pair.

Graphics processing units (GPUs) embrace many-core compute devices where massively parallel compute threads are offloaded from CPUs. This heterogeneous nature of GPU computing raises non-trivial data transfer problems especially against latency-critical real-time systems. However even the basic characteristics of data transfers associated with GPU computing are not well studied in the literature. In this paper, we investigate and characterize currently-achievable data transfer methods of cutting-edge GPU technology. We implement these methods using open-source software to compare their performance and latency for real-world systems. Our experimental results show that the hardware-assisted direct memory access (DMA) and the I/O read-and-write access methods are usually the most effective, while on-chip micro controllers inside the GPU are useful in terms of reducing the data transfer latency for concurrent multiple data streams. We also disclose that CPU priorities can protect the performance of GPU data transfers.

We propose a robust seamless communication architecture that enables legacy mobile terminal software designed for single-CPU processors to be run on multi-CPU processors without any software modifications. This architecture features two new technologies: proxy processes, which help achieve the design of its user-level system-call hooking and a robust design method, which reduces bandwidth variation by systematic parameter optimization. Our evaluations confirmed that this architecture achieves fundamental features with satisfactory performance, that we have succeeded in getting actual mobile terminal software to run on three CPUs without modifying the software, and that the robust design method reduces bandwidth variation by 21%.

Fundamental algorithms should be parallelized to accelerate EDA software on multi-core architecture. In this paper, we introduce scalable algorithms that have scalability on multi-cores. As an example, a sorting algorithm, called Map Sort, is presented. This algorithm uses a map from subsets of input data to intervals on data range. Experimental results show that, in comparison with quick sort on a single CPU, processing time of Map Sort is comparable on a CPU and three times faster on four CPUs.

We propose a method for dynamic security-domain scaling on SMPs that offers both highly scalable performance and high security for future high-end embedded systems. Its most important feature is its highly efficient use of processor resources, accomplished by dynamically changing the number of processors within a security-domain (i.e., dynamically yielding processors to other security-domains) in response to application load requirements. Two new technologies make this scaling possible without any virtualization software: (1) self-transition management and (2) unified virtual address mapping. Evaluations show that this domain control provides highly scalable performance and incurs almost no performance overhead in security-domains. The increase in OSs in binary code size is less than 1.5%, and the time required for individual state transitions is on the order of a single millisecond. This scaling is the first in the world to make possible the dynamic changing of the number of processors within a security-domain on an ARM SMP.

We propose a secure platform on a chip multiprocessor, FIDES, in order to enable next generation mobile terminals to execute downloaded native applications for Linux. Its most important feature is the higher security based on multigrained separation mechanisms. Four new technologies support the FIDES platform: bus filter logic, XIP kernels, policy separation, and dynamic access control. With these technologies, the FIDES platform can tolerate both application-level and kernel-level bugs on an actual download subsystem. Thus, the best-suited platform to secure next generation mobile terminals is FIDES.

We propose a processor virtualization architecture, VIRTUS, to provide a dedicated domain for preinstalled applications and virtualized domains for downloaded native applications. With it, security-oriented next-generation mobile terminals can provide any number of domains for native applications. VIRTUS features three new technologies, namely, VMM asymmetrization, dynamic interdomain communication (IDC), and virtualization-assist logic, and it is first in the world to virtualize an ARM-based multiprocessor. Evaluations have shown that VMM asymmetrization results in significantly less performance degradation and LOC increase than do other VMMs. Further, dynamic IDC overhead is low enough, and virtualization-assist logic can be implemented in a sufficiently small area.

Reliability of embedded systems can be enhanced by multicore and partitioning approaches. Physical partitioning based on AMP multicore achieves runtime stability of multiple applications in a system and prevents the whole system shutdown as well even when a malicious code creeps in. Combined with logical partitioning by processor visualization and SMP technologies, the multicore architecture could realize more flexible and more scalable platform for future embedded systems.

We propose a new processor virtualization architecture, VIRTUS, to provide a dedicated domain for pre-installed applications and virtualized domains for downloaded native applications. With it, security-oriented next-generation mobile terminals can provide any number of domains for native applications. VIRTUS features three new technologies: VMM asymmetrization, dynamic inter-domain communication and virtualization-assist logic, and it is first in the world to virtualize an ARM-based multiprocessor.

As the interconnection delays control the LSI performance, the LSI performance estimation at higher design level becomes more difficult. In this paper a new LSI performance model for the estimation is described, which is made up by adopting a new clock-skew model to the SUSPENS (Stanford University System Performance Simulator) model. Using the model, it is cleared that a specific block size, where the line delay overcomes the block cycle time, becomes shorter as the LSI generation proceeds.

A clock buffer placement algorithm is proposed for future technologies in which wire delay dominates signal delay. In such technologies, buffers need to be placed so as to minimize the maximum wire delay. We formulate the problem into a non-linear programming, and solve it by an iteration method with a randomized technique. We applied our buffer placement algorithm with a zero-skew router to several benchmark data, and show that our algorithm achieves 30% less delay time than a H-tree based algorithm.

Abstract | A bucket algorithm is proposed for zeroskew routing with linear time complexity on the average. Our algorithm is much simpler and more e cient than the best known algorithm which uses Delaunay triangulations for segments on Manhattan distance. Experimental results show that the linearity of our algorithm is accomplished. Our algorithm generates a zero-skew routing for 3000-pin benchmark data within 5 seconds on a 90MIPS RISC workstation. I.

A zero-skew routing algorithm with clustering and improvement methods is proposed. This algorithm generates a zero-skew routing in O(n log n) time for n pins, and it is proven that the order of the total wire length is best possible. Our algorithm achieves 20% reduction of the total wire length and 15%-50% improvement of the delay time on benchmark data compared with the best known algorithm. 1 Department of Computer Science, Princeton University and C&C Systems Research Laboratories, NEC Corporation 1 Introduction Designing zero-skew routings with minimal delay time is one of the most crucial issues in current and future performance-driven layouts. In synchronous circuits, the clock skew t skew limits the clock period t c together with data path delay t d and other constant factors t const . The following equation formulates the clock period: t c = t skew + t d + t const : Therefore, in order to optimize the clock period, the clock skew needs to be minimized. In addition, in desi...

VLSI chips for luminance/chrominance (Y/C) signal separation and synthesis have been developed. Application-specific FIR filter structures and canonical signed-digit representation (CSR) multipliers used in the filters make it possible to develop compact high-speed VLSI chips. A silicon compiler, which employs the optimal FIR filter structures and supplies the optimal filter design faculty, has contributed to quick VLSI development. Y/C signal separation using four video FIR filters and Y/C signal synthesis using three video FIR filters are implemented on single chips by 1.2- mu m CMOS technology.>

New placement and global routing algorithms are proposed for standard cell layouts. The placement algorithm, called the hierarchical clustering with min-cut exchange (HCME), is effective to avoid being trapped in local optimum solutions. The global routing algorithm does not route the nets one by one and therefore, the results are independent of the net order and channel order. In this algorithm, channel width is minimized under a cost function, in which the trade-off between the minimization of net lengths and the minimization of the number of tracks is considered. These algorithms are simple and highly efficient. This is confirmed by computational experiments.

A novel algorithm is presented for the clock net reassignment problem in semi-custom layout design. The clock net reassignment is used to shorten clock nets by reconnecting clock drivers and flip-flops so as to obtain high performance LSIs. The proposed algorithm, by using the Voronoi diagram in computational geometry, is quite efficient and gives better assignments than existing techniques. The experimental results show that the algorithm yields a 10% reduction in net lengths in comparison with existing algorithms. The algorithm takes only 18 s to find an assignment for 167 drivers and 833 flip-flops.>

The orthogonal segment intersection search problem is stated as follows: Given a set S of n orthogonal segments in the plane, report all the segments of S that intersect a given orthogonal query segment. For this problem, we propose a simple and practical algorithm based on bucketing techniques. It constructs, in Ο(n) time preprocessing, a search structure of size Ο(n) so that all the segments of S intersecting a query segment can be reported in Ο(k) time in the average case, where k is the number of the reported segments. The proposed algorithm as well as existing algorithms is implemented in FORTRAN, and their practical efficiencies are investigated through computational experiments. It is shown that our Ο(k) search time, Ο(n) space and Ο(n) preprocessing time algorithm is practically the most efficient among the tested algorithms.

article Free Access Share on A new point-location algorithm and its practical efficiency: comparison with existing algorithms Author: Ta. Asano Department of Mathematical Engineering and Instrumentation Physics, Faculty of Engineering, University of Tokyo, Bunkyo-ku, Tokyo, Japan 113 Department of Mathematical Engineering and Instrumentation Physics, Faculty of Engineering, University of Tokyo, Bunkyo-ku, Tokyo, Japan 113View Profile Authors Info & Claims ACM Transactions on GraphicsVolume 3Issue 2April 1984 pp 86–109https://doi.org/10.1145/357337.357338Published:01 April 1984Publication History 52citation921DownloadsMetricsTotal Citations52Total Downloads921Last 12 Months43Last 6 weeks13 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