標題: A SYSTOLIC ALGORITHM FOR DYNAMIC-PROGRAMMING
作者: LIN, CJ
交大名義發表
應用數學系
National Chiao Tung University
Department of Applied Mathematics
公開日期: 1-一月-1994
摘要: We present a formal systolic algorithm to solve the dynamic programming problem for an optimal binary search tree. For a fixed integer j such that 2 less-than-or-equal-to j less-than-or-equal-to n, first we derive a linear systolic array to evaluate the minimal cost c(i,j) for 1 less-than-or-equal-to i < j. Then we combine these (n - 1) linear systolic arrays to form a two-dimensional systolic array. The computational model consists of inverted right perpendicular (n2 + 2n - 4)/4 inverted left perpendicular processing elements. The algorithm requires (2n - 3) time steps to solve this problem. The elapsed time within a time step is independent of the problem size n. It is suitable for the VLSI implementation due to the identical and simple structure of processing elements. We also prove the correctness of this algorithm by induction.
URI: http://hdl.handle.net/11536/2718
ISSN: 0898-1221
期刊: COMPUTERS & MATHEMATICS WITH APPLICATIONS
Volume: 27
Issue: 1
起始頁: 1
結束頁: 10
顯示於類別:期刊論文


文件中的檔案:

  1. A1994MJ43100001.pdf