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

16th Euromicro Conference on Digital System Design (DSD)

作者： Wakaba, Yoichi Nagayama, Shinobu Wakabayashi, Shin'ichi Inagi, Masato Hiroshima City Univ Grad Sch Informat Sci Asaminami Ku Hiroshima 7313194 Japan

ISBN: (纸本)9780769550749

This paper proposes a method using partial reconfiguration to realize a compact regular expression matching engine, which can update a pattern quickly. In the proposed method, several partial circuits, each of which handles a different class of regular expressions, are provided in advance. When a regular expression pattern is given, a suitable and compact matching engine is implemented on FPGA by combining the partial circuits according to the given pattern and using partial reconfiguration. The method can update a pattern quickly, since it does not need re-design of a circuit resulting in a long time for pattern update. Experimental results show that the proposed method reduces 63% circuit size of an existing engine without increasing pattern updating time.

关键词： regular expression matching partial reconfiguration FPGA systolic algorithm

来源：评论

学校读者我要写书评

暂无评论

An efficient and hardware-implementable systolic algorithm for the longest common subsequence problem

An efficient and hardware-implementable systolic algorithm f...

引用

7th International Conference on Machine Learning and Cybernetics

作者： Hu, Shu-Hua Wang, Cong-Wei Chen, Hsing-Lung Jiwen Univ Sci & Tech Dept Comp Sci & Informat Engn Taipei Taiwan Natl Taiwan Univ Sci & Technol Dept Elect Engn Taipei Taiwan

ISBN: (纸本)9781424420957

The problem of longest common subsequence is defined as finding the longest common subsequence of two input sequences. It can be employed in many fields such as speech and signal processing, data compression, syntactic pattern recognition, string processing, and genetic engineering. Usually, lengths of both input sequences are very long, resulting in long processing time. Many previous algorithms have been proposed to reduce the processing time. Previous systolic algorithms can achieve linear time complexity with linear number of processing elements. However, each processing element needs linear memory-space to store intermediate results and then the system needs too large memory-space in total, resulting in being not suitable for being implemented on VLSI. Hence, to design an efficient and hardware-implementable algorithm is an important issue. This paper proposes a hardware-implementable and efficient systolic algorithm for the longest common subsequence problem. At first, we investigate the property of overlapped-contours. By employing "divide and conquer" technique, we can rind a longest common subsequence from the overlapped-contours. It needs a little more time complexity with only linear memory-space in total. Furthermore, the number of physical processing elements can be fixed by employing the concept of virtual processing elements. Therefore, our proposed systolic algorithm is not only hardware-implementable on VLSI but also efficient.

关键词： longest common subsequence systolic algorithm divide and conquer virtual processing elements

来源：评论

学校读者我要写书评

暂无评论

Review on FPGA- based systolic Poisson Solver

Review on FPGA- based Systolic Poisson Solver

引用

International Conference on Computer Technology and Development

作者： Yee, Ngoh Jin Othman, Mohamed Univ Putra Malaysia Dept Commun Technol & Network Upm Serdang 43400 Selangor Malaysia

ISBN: (纸本)9780769538921

Many important scientific calculation involve large computation time, some are greater than a human lifespan. Parallelism offers to make these previously impractical solution techniques feasible. Physical phenomena such as the electromagnetic and the incompressible potential flow fields are presented in elliptic equation, typical representative by Poisson's equation. The four points modified explicit group (MEG) introduced by M. Othman and A. R. Abdullah [1] and concept of systolic computation evolved to produce practical and low- cost parallel processing for latter problem.

关键词： FPGA systolic algorithm Poisson equation

来源：评论

学校读者我要写书评

暂无评论

An Implementation of MacMahon's Partition Analysis in Ordering the Number of Lattice Points in Convex Polyhedron with Examples for systolic Arrays

An Implementation of MacMahon's Partition Analysis in Orderi...

引用

31st International Conference on Information Technology Interfaces

作者： Snopce, Halil Spahiu, Ilir South East European Univ CST Fac 1200 Ilindenska Bb Tetovo Macedonia Ss Cyril & Methodius Univ Fac Pedag Ss Clement Ohrid Skopje Macedonia

ISBN: (纸本)9789537138158

We have investigated the "Omega calculus", as a computational method for solving problems via their corresponding Diophantine relation. These methods can be applied for the problems related with the number of lattice points in polyhedron, positively in our case for systolic array computations. From the corresponding systolic algorithm we form a system of linear diophantine equalities using the domain of computation which is given by the set of lattice points inside the polyhedron. Then we run the Mathematica program DiophantineGF.m. This program calculates the generating function from which is possible to find the number of solutions to the system of Diophantine equalities, which in fact gives the lower bound for the number of processors needed for the corresponding algorithm. There is given a mathematical explanation of the problem as well. We illustrate this for finding the lower bound of the systolic algorithm for Discrete Fourier transformation (DFT).

关键词： systolic array nested loop algorithm systolic algorithm Polyhedron generating function system of Diophantine equations index space lattice points lower bound of processor elements Omega calculus

来源：评论

学校读者我要写书评

暂无评论

A systolic Architecture with Linear Space Complexity for Longest Common Subsequence Problem

A Systolic Architecture with Linear Space Complexity for Lon...

引用

IEEE 8th International Conference on ASIC

作者： Chen, Chuanpeng Qin, Zhongping Wuhan Univ Sch Comp Wuhan 430072 Hubei Peoples R China

ISBN: (纸本)9781424438686

The longest common subsequence (LCS) problem is to find an LCS of two strings and the length of the LCS (LLCS). Many previous works focused on reducing the processing time. However, most require too large memory space in total, resulting in being not suitable for hardware implementation. In this paper, we propose a hardware-implementable algorithm and its systolic architecture. The algorithm achieves linear space complexity, and the systolic architecture is feasible for hardware implementation. For two given strings with their lengths of m and n, the algorithm consumes less time complexity when the LLCS is approaching to the minimum of m and n. Furthermore, a scalable architecture is proposed to deal with the LCS problems of two huge strings, whose lengths are far more than m and n. Therefore, our scalable systolic architecture with linear space complexity for the LCS problem is suitable for hardware implementation, and the synthesized results show that our architecture is more efficient.

关键词： Longest common subsequence systolic algorithm systolic architecture scalable architecture

来源：评论

学校读者我要写书评

暂无评论

FPGA generators of combinatorial configurations in a linear array model

FPGA generators of combinatorial configurations in a linear ...

引用

7th International Symposium on Parallel and Distributed Computing

作者： Kokosinski, Zbigniew Halesiak, Pawel Cracow Univ Technol Fac Elect & Comp Eng PL-31155 Krakow Poland

ISBN: (纸本)9780769534725

In this paper we describe hardware implementations of generators of combinatorial objects. For implementation several systolic algorithms were selected that generate combinatorial configurations in a linear array model. The algorithms generate such objects as combinations, combinations with repetitions, t-ary trees, partitions, and variations with repetitions. The generators were implemented in VHLD with Xilinx Foundation ISE, software and tested on Digilent development boards with Xilinx FPGAs. Implementation data obtained for various input parameters and FPGA devices are given.

关键词： combinatorial objects parallel generation linear array systolic algorithm FPGA generator

来源：评论

学校读者我要写书评

暂无评论

DERIVING A FAST systolic algorithm FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM

引用

Parallel algorithms and Applications 2002年第1期17卷 1-18页

作者： Yen-Chun Lin[a] Jih-Wei Yeh[a] [a] Dept. of Electronic Engineering National Taiwan University of Science and Technology Taipei Taiwan

The longest common subsequence (LCS) problem is to find an LCS of two given sequences and the length of the LCS. In this paper, an efficient systolic algorithm for the LCS problem is derived. For two sequences of length m and n, where m ≥ n, the problem can be solved with only [n/2] processors in m + 2[n/2] − 1 time steps. Compared with other systolic algorithms that solve the LCS problem, our algorithm not only takes fewer time steps but also uses fewer processors. Our algorithm is better suited to implementation on multicomputers than other systolic algorithms.

关键词： Longest common subsequence Multicomputer systolic algorithm C. 1.4 [Parallel Architectures] D. 1.3 [Concurrent Programming]

来源：评论

学校读者我要写书评

暂无评论

systolic and hyper-systolic algorithms for the gravitational N-body problem, with an application to Brownian motion

引用

JOURNAL OF COMPUTATIONAL PHYSICS 2003年第2期185卷 484-511页

作者： Dorband, EN Hemsendorf, M Merritt, D Rutgers State Univ Dept Phys & Astron New Brunswick NJ 08903 USA

A systolic algorithm rhythmically computes and passes data through a network of processors. We investigate the performance of systolic algorithms for implementing the gravitational N-body problem on distributed-memory computers. systolic algorithms minimize memory requirements by distributing the particles between processors. We show that the performance of systolic routines can be greatly enhanced by the use of non-blocking communication, which allows particle coordinates to be communicated at the same time that force calculations are being carried out. The performance enhancement is particularly great when block sizes are small, i.e., when only a small fraction of the N particles need their forces computed in each time step. Hyper-systolic algorithms reduce the communication complexity from O(Np), with p the processor number, to O(Nrootp), at the expense of increased memory demands. We describe a hyper-systolic algorithm that will work with a block time step algorithm and analyze its performance. As an example of an application requiring large N, we use the systolic algorithm to carry out direct-summation simulations using 1 ()6 particles of the Brownian motion of the supermassive black hole at the center of the Milky Way galaxy. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： systolic algorithm gravitational N-body problem Brownian motion

来源：评论

学校读者我要写书评

暂无评论

Analysis of Parallel Matrix Multiplication algorithms

Analysis of Parallel Matrix Multiplication Algorithms

引用

2004 International Symposium on Distributed Computing and Applications to Business, Engineering and Science

作者： Wanlong Liu Yaolin Gu Southern Yangtze University Wuxi,Jiangsu,214036,PR of China

Matrix multiplication is the fundamental operation in many numerical linear algebra *** efficient implementation on parallel high performance computers, together with the implementation of other basic linear algebra operations,is an issue of primary importance for providing these systems with scientific software libraries. Consequently,considerable effort has been devoted to development of efficient practical parallel matrix multiplication *** this paper,we describe performance analysis of a simple parallel algorithm, Cannon's algorithm,systolic algorithm and hyper-systolic *** analysis indicates that the performance of the hyper-systolic algorithm outperforms the other algorithms.

关键词： Matrix Multiplication Performance Analysis Cannon's algorithm systolic algorithm Hyper-systolic algorithm

来源：评论

学校读者我要写书评

暂无评论

A systolic image difference algorithm for RLE-compressed images

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2000年第5期11卷 433-443页

作者： Ercal, F Allen, M Feng, H Univ Missouri Dept Comp Sci Rolla MO 65401 USA Hewlett Packard Richardson TX 75080 USA Microsoft Corp Redmond WA 98052 USA

A new systolic algorithm which computes image differences in run-length encoded (RLE) format is described. The binary image difference operation is commonly used in many image processing applications including automated inspection systems, character recognition, fingerprint analysis, and motion detection. The efficiency of these operations can be improved significantly with the availability of a fast systolic system that computes the image difference as described in this paper. It is shown that for images with a high similarity measure, the time complexity of the systolic algorithm is small and, in some cases, constant with respect to the image size. A formal proof of correctness for the algorithm is also given.

关键词： systolic algorithm image difference image compression run-length encoding

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：