检索结果-内蒙古大学图书馆

Optimal algorithms for the channel-assignment problem on a reconfigurable array of processors with wider bus networks

引用

IEEE TRANSACTIONS ON parallel AND DISTRIBUTED SYSTEMS 2002年第11期13卷 1124-1138页

作者： Horng, SJ Tsai, HR Pan, Y Seitzer, J Natl Taiwan Univ Sci & Technol Dept Comp Sci & Informat Engn Taipei 106 Taiwan Ling Tung Coll Dept Informat Management Taichung Taiwan Georgia State Univ Dept Comp Sci Atlanta GA 30303 USA Univ Dayton Dept Comp Sci Dayton OH 45469 USA

The computation model on which the algorithms are developed is the reconfigurable array of processors with wider bus networks (abbreviated to RAPWBN). The main difference between the RAPWBN model and other existing reconfigurable parallel processing systems is that the bus width of each network is bounded within the range [2, [rootN]]. Such a strategy not only saves the silicon area of the chip as well as increases the computational power enormously, but the strategy also allows the execution speed of the proposed algorithms to be tuned by the bus bandwidth. To demonstrate the computational power of the RAPWBN, the channel-assignment problem is derived in this paper. For the channel-assignment problem with N pairs of components, we first design an O(T + [N/w]) time parallel algorithm using 2N processors with a 2N-row by 2N-column bus network, where the bus width of each bus network is w-bit for 2 less than or equal to w less than or equal to [rootN] and T = [log(w) N] + 1. By tuning the bus bandwidth to the natural log N-bit and the extended N-1/c-bit (N-1/c > log N) for any constant c and c greater than or equal to 1, two more results which run in O(log N/ log log N) and O(1) time, respectively, are also derived. When compared to the algorithms proposed by Olariu et al. [17] and Lin [14], it is shown that our algorithm runs in the equivalent time complexity while significantly reducing the number of processors to O(N).

关键词： channel-assignment problem minimum coloring problem interval graph list ranking integer sorting parallel algorithm reconfigurable array of processors with wider bus networks

来源：评论

学校读者我要写书评

暂无评论

Splitting extrapolation for solving second order elliptic systems with curved boundary in R^d by using d-quadratic isoparametric finite element

引用

APPLIED NUMERICAL MATHEMATICS 2002年第4期40卷 467-481页

作者： Tao, L Lu, J So Alberta Inst Technol Dept Energy Calgary AB Canada Sichuan Univ Math Coll Chengdu 610064 Peoples R China

Splitting extrapolation for solving second order elliptic systems with curved boundary in R-d by using isoparametric d-quadratic element Q(2) is presented, which is a new technique for solving large scale scientific and engineering problems in parallel. By means of domain decomposition, a large scale multidimensional problem with curved boundary is turned into many discrete problems involving several grid parameters. The multivariate asymptotic expansions of isoparametric d-quadratic Q(2) finite element errors with respect to independent grid parameters are proved for second order elliptic systems. Therefore after solving smaller problems with similar sizes in parallel. a global fine grid approximation with higher accuracy is computed by the splitting extrapolation method. (C) 2001 Published by Elsevier Science B.V. on behalf of IMACS.

关键词： splitting extrapolation domain decomposition parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

Efficient graph-theoretic algorithms on a linear array with a reconfigurable pipelined bus system

引用

JOURNAL OF SUPERCOMPUTING 2002年第2期23卷 193-211页

作者： Datta, A Univ Western Australia Dept Comp Sci & Software Engn Perth WA 6009 Australia Univ Freiburg Inst Informat D-7800 Freiburg Germany

We present efficient algorithms for solving several fundamental graph-theoretic problems on a Linear Array with a Reconfigurable Pipelined Bus System (LARPBS), one of the recently proposed models of computation based on optical buses. Our algorithms include finding connected components, minimum spanning forest, biconnected components, bridges and articulation points for an undirected graph. We compute the connected components and minimum spanning forest of a graph in O(log n) time using O(m+n) processors where m and n are the number of edges and vertices in the graph and m=O(n(2)) for a dense graph. Both the processor and time complexities of these two algorithms match the complexities of algorithms on the Arbitrary and Priority CRCW PRAM models which are two of the strongest PRAM models. The algorithms for these two problems published by Li et al. [7] have been considered to be the most efficient on the LARPBS model till now. Their algorithm [7] for these two problems require O(log n) time and O(n(3)/log n) processors. Hence, our algorithms have the same time complexity but require less processors. Our algorithms for computing biconnected components, bridges and articulation points of a graph run in O(log n) time on an LARPBS with O(n(2)) processors. No previous algorithm was known for these latter problems on the LARPBS.

关键词： parallel algorithm optical computing reconfigurable pipelined bus graph algorithms connected components minimum spanning forest biconnected components

来源：评论

学校读者我要写书评

暂无评论

A fast implementation of correlation of long data sequences for coherent receivers

引用

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS II-EXPRESS BRIEFS 2002年第6期49卷 430-433页

作者： Bhattacharya, C Patel, G DRDO DEAL Dehra Dun 248001 Uttar Pradesh India

Coherent reception depends upon matching of phase between the transmitted and received signal. Fast convolution techniques based on fast Fourier tansform (FFT) are widely used for extracting time delay information from such matching. The latency in processing a large data window of the received signal is a serious overhead for mission critical real time applications. The implementation of a parallel algorithm for correlation of long data sequences in multiprocessor environment is demonstrated here. The algorithm does processing while acquiring the received signal and reduces the computation overhead considerably because of inherent parallelism.

关键词： block correlator coherent multiprocessor parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

Local block factorization and its parallelization to block tridiagonal matrices 5

Local block factorization and its parallelization to block t...

引用

5th International Conference on algorithms and Architectures for parallel Processing

作者： Wu, JP Li, XM Natl Univ Def Technol Sch Comp Changsha 410073 Peoples R China

ISBN: (纸本)0769515126

A type of incomplete decomposition preconditioner based on local block factorization is considered, for the matrices derived from discreting 2-D or 3-D elliptic partial differential equations. We prove that the condition numbers of the preconditioned matrices are small, which means that the constructed preconditioners are effective. Further we consider an efficient parallel version of the preconditioner which depends only on a single integer argument. When its value is small, the iterations needed on multiple processors to converge is much more than on a single processor But with the increase of this value, the difference decreases step by step. Finally, we have many experiments on a cluster of 6 PCs with main frequencies of 1.8GHz The results show that the local block factorizations constructed are efficient in serial implementation, if compared to some well-known effective preconditioners, and the parallel versions are efficient also.

关键词： block LU decomposition parallel algorithm incomplete factorization M matrix preconditioner

来源：评论

学校读者我要写书评

暂无评论

Study on High-Performance Computing for Simulation of End Milling Force

引用

厦门大学学报（自然科学版） 2002年第S1期41卷 183-184页

作者： ZHANG Zhi-hai, ZHENG Li, LI Zhi-zhong, LIU Da-cheng, ZHAN G Bo-peng (Department of Industry Engineering, Tsinghua University, Beijing 1000 84, China)

Milling Process Simulation is one of the important re search areas in manufacturing science. For the purpose of improving the prec ision of simulation and extending its usability, numerical algorithm is more and more used in the milling modeling areas. But simulative efficiency is decreasin g with increase of its complexity. As a result, application of the method is lim ited. Aimed at above question, high-efficient algorithm for milling process sim ulation is studied. It is important for milling process simulation’s applicatio n. parallel computing is widely used to solve the large-scale computation question s. Its advantages include system flexibility, robust, high-efficient computing capability and high ratio of performance to price. With the development of compu ter network, utilizing the computing resource in the Internet, a virtual computi ng environment with powerful computing capability can be consisted by microc omputers, and the difficulty of building hardware environment which is used to s upport parallel computing is reduced. How to use network technology and parallel algorithm to improve simulative effic iency for milling forces simulation is investigated in the paper. In order to pr edict milling forces, a simplified local milling forces model is used in the pap er. End milling cutter is assumed to be divided by r number of differential elem ents along the axial direction of the cutter. For a given time, the total cuttin g forces can be obtained by summarizing the resultant cutting force produced by each differential cutter disc. Divide the whole simulative time into some segmen ts, send these program’s segments to microcomputers in the Internet and obtain the result of the program’s segments, all of the result of program’s segments a re composed the final result. For implementing the algorithm, a distributed parallel computing framework is de signed in the paper. In the framework, web server plays a role of controller. Us ing Java RMI(remote method int

关键词： end-milling force model simulation high-perfo rmance computing parallel algorithm Java RMI

来源：评论

学校读者我要写书评

暂无评论

Constraint directed CAD tool for automatic latency-optimal implementation of 1-D and 2-D Fourier transforms

Constraint directed CAD tool for automatic latency-optimal i...

引用

Conference on Reconfigurable Technology - FPGAs and Reconfigurable Processors for Computing and Communications IV

作者： Nash, JG CENTAR (United States)

ISBN: (纸本)0819446467

A specialized CAD tool is described that will take a user's high level code description of a non-uniform affinely indexed algorithm and automatically generate abstract latency-optimal systolic arrays. Emphasis has been placed on ease of use and the ability to either force conformation to specific design criteria or perform unconstrained explorations. How such design goals are achieved is illustrated in the context of LU decomposition and the matrix Lyapunov equation. The tool is then used to generate new I-D and 2-D hardware efficient systolic arrays for the discreet Fourier transform that take advantage of the use of the radix-4 matrix decomposition.

关键词： signal and image processing FPGA CAD tool systolic DFT FFT parallel algorithm algorithm mapping

来源：评论

学校读者我要写书评

暂无评论

Lossless compression of very large volume data with fast dynamic access 3

Lossless compression of very large volume data with fast dyn...

引用

Conference on Electronic Imaging and Multimedia Technology III

作者： Zhao, RK Tao, T Gabriel, M Belford, GG Univ Illinois Dept Comp Sci Urbana IL 61801 USA

ISBN: (纸本)0819447145

The volumetric data set is important in many scientific and biomedical fields. Since such sets may be extremely large, a compression method is critical to store and transmit them. To achieve a high compression rate, most of the existing volume compression methods are lossy, which is usually unacceptable in biomedical applications. We developed a new context-based non-linear prediction method to preprocess the volume data set in order to effectively lower the prediction entropy. The prediction error is further encoded using Huffman code. Unlike the conventional methods, the volume is divided into cubical blocks to take advantage of the data's spatial locality. Instead of building one Huffman tree for each block, we developed a novel binning algorithm that build a Huffman tree for each group (bin) of blocks. Combining all the effects above, we achieved an excellent compression rate compared to other lossless volume compression methods. In addition, an auxiliary data structure, Scalable Hyperspace File (SHSF) is used to index the huge volume so that we can obtain many other benefits including parallel construction, on-the-fly accessing of compressed data without global decompression, fast previewing, efficient background compressing, and scalability etc.

关键词： volume data medical imaging out-of-core processing lossless compression octree entropy coding predictive coding dynamic decompression parallel algorithm Hilbert curve

来源：评论

学校读者我要写书评

暂无评论

Brain slicer: A high performance Internet-based neuro-medical Imaging system

Brain slicer: A high performance Internet-based neuro-medica...

引用

Conference on Visualization and Data Analysis 2002

作者： Zhao, RK Tao, T Gabriel, M Belford, GG Univ Illinois Dept Comp Sci Urbana IL 61801 USA Univ Illinois Beckman Inst Urbana IL 61801 USA

ISBN: (纸本)0819444057

In this paper, we present a neuro-medical imaging system called the Brain Slicer, which allows neuroscientists to construct a three-dimensional digital brain atlas from an array of high-resolution parallel section images and obtain arbitrary oblique section images from the digital atlas. This application is based on a new data structure, the Scalable Hyper-Space File (SHSF). The SHSF is a generalized data structure that can represent a hyperspace of any dimension. The two-dimensional SHSF is a scalable linear quadtree and the three-dimensional SHSF is a scalable linear octree. Unlike the normal linear quadtree and octree, the data structure uses a scalable linear coding scheme. It recursively uses fixed-length linear code to encode the hyperspace, which is efficient in terms of storage space and accessing speed. The structure lends itself well to pipelined parallel operations in constructing the volumetric data set, so that it enjoys excellent performance even though the huge data set imposes heavy disk I/O requirements. The data structure can provide different levels of detail;therefore it can be used in an environment where the bandwidth and computation power is limited, such as the Internet and slow desktop computers. We envision that this methodology can be used in many areas other than neuro-medical imaging.

关键词： neuroinformatics digital atlas octree quadtree parallel algorithm medical imaging brain file structure levels of detail Internet

来源：评论

学校读者我要写书评

暂无评论

Optimal parallel Weighted Multiselection

Optimal Parallel Weighted Multiselection

引用

2002年IEEE十区计算机、通信、控制和电机工程会议

作者： Hong Shen Graduate School of Information Science Japan Advanced Institute of Science and Technology 1-1 Asahidai, Tatsunokuchi, Ishikawa 923-1292, Japan

Weighted multiselection requires to select r elementsfrom a given set of n elements, each associated witha weight, such that each element selected is on apre-specified weighted-rank, where an element is onweighted-rank k if it is the smallest element such thatthe aggregated weight of all elements not greater than itin the set is not smaller than *** paper pressents ef-ficient algorithms for solving this problem both sequen-tially and in parallel on EREW PRAM. Our sequentialalgorithm solves this problem in time O（nlogr） whichis optimal. Our parallel algorithm runs in O（T log r）time on an EREW PRAM with 1

关键词： EREW PRAM multiselection parallel algorithm selection weight selection sorting

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：