東華大學圖書館 |

語系: 繁體中文

說明(常見問題)

回圖書館首頁

手機版館藏查詢

登入

回首頁

切換: 標籤 | MARC模式 | ISBD

Algorithms and data structures for c...

Chowdhury, Rezaul Alam.

FindBook

Google Book

Amazon

博客來

Algorithms and data structures for cache-efficient computation: Theory and experimental evaluation.

紀錄類型:	書目-語言資料,印刷品 : Monograph/item
正題名/作者:	Algorithms and data structures for cache-efficient computation: Theory and experimental evaluation./
作者:	Chowdhury, Rezaul Alam.
面頁冊數:	255 p.
附註:	Adviser: Vijaya Ramachandran.
Contained By:	Dissertation Abstracts International68-07B.
標題:	Biology, Bioinformatics. -
電子資源:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3274775
ISBN:	9780549138952

Algorithms and data structures for cache-efficient computation: Theory and experimental evaluation.
Chowdhury, Rezaul Alam.

Algorithms and data structures for cache-efficient computation: Theory and experimental evaluation. - 255 p.

Adviser: Vijaya Ramachandran.

Thesis (Ph.D.)--The University of Texas at Austin, 2007.

The ideal-cache model is an abstraction of the memory hierarchy in modern computers which facilitates the design of algorithms that can use the caches (i.e., memory levels) in the hierarchy efficiently without using the knowledge of cache parameters. In addition to possibly running faster than traditional flat-memory algorithms due to reduced cache-misses, these cache-oblivious algorithms are also system-independent and thus more portable than cache-aware algorithms. These algorithms are useful both in applications that work on massive datasets and in applications that run on small-memory systems such as handheld devices.

ISBN: 9780549138952Subjects--Topical Terms:

1018415
Biology, Bioinformatics.

Algorithms and data structures for cache-efficient computation: Theory and experimental evaluation.
LDR:04297nam 2200325 a 45 001 947662
005 20110524
008 110524s2007 ||||||||||||||||| ||eng d
020 $a 9780549138952
035 $a (UMI)AAI3274775
035 $a AAI3274775
040 $a UMI $c UMI
100 1 $a Chowdhury, Rezaul Alam. $3 1271134
245 1 0 $a Algorithms and data structures for cache-efficient computation: Theory and experimental evaluation.
300 $a 255 p.
500 $a Adviser: Vijaya Ramachandran.
500 $a Source: Dissertation Abstracts International, Volume: 68-07, Section: B, page: 4585.
502 $a Thesis (Ph.D.)--The University of Texas at Austin, 2007.
520 $a The ideal-cache model is an abstraction of the memory hierarchy in modern computers which facilitates the design of algorithms that can use the caches (i.e., memory levels) in the hierarchy efficiently without using the knowledge of cache parameters. In addition to possibly running faster than traditional flat-memory algorithms due to reduced cache-misses, these cache-oblivious algorithms are also system-independent and thus more portable than cache-aware algorithms. These algorithms are useful both in applications that work on massive datasets and in applications that run on small-memory systems such as handheld devices.
520 $a The major contribution of this dissertation is a number of new cache-efficient and cache-oblivious algorithms and data structures for problems in three different domains: graph algorithms, problems in the Gaussian Elimination Paradigm (GEP), and problems with dynamic programming algorithms. Among graph problems we concentrate on shortest path computation, and for the computation-intensive problems in the latter two domains we also present efficient parallelizations of our cache-oblivious algorithms for distributed and shared caches. We perform extensive experimental study of most of our algorithms, and compare them with best known existing algorithms and software.
520 $a In the area of graph algorithms and data structures, we introduce the first efficient cache-oblivious priority queue supporting Decrease-Key operations, and use it to obtain the first non-trivial cache-oblivious single-source shortest path algorithms for both directed and undirected graphs with general non-negative edge-weights. Our experimental results show that shortest path computation using a light-weight version of this new priority queue is faster than using highly optimized traditional priority queues even when the computation is in-core. We also present several new cache-efficient exact and approximate all-pairs shortest path algorithms for both weighted and unweighted undirected graphs.
520 $a The Gaussian Elimination Paradigm (GEP) includes many important practical problems with constructs similar to that in Gaussian elimination without pivoting, e.g., Floyd-Warshall's all-pairs shortest path, LU decomposition without pivoting, matrix multiplication, etc. We present a general cache-oblivious framework for cache-efficient sequential and parallel solution of any problem in GEP. Our experimental results comparing our cache-oblivious algorithms with industrial-strength cache-aware BLAS (i.e., Basic Linear Algebra Subprogram) code suggest that our GEP framework offers an attractive trade-off between efficiency and portability.
520 $a In the domain of dynamic programs, we present efficient cache-oblivious sequential and parallel algorithms for a number of important dynamic programs in bioinformatics including optimal pairwise sequence alignment, median of three sequences, and RNA secondary structure prediction with and without (simple) pseudo-knots. All our algorithms improve significantly over the cache complexity of earlier algorithms, and either match or improve over their space complexity. We empirically compare most of our algorithms with the best publicly available code written by others, and our experimental results indicate that our algorithms run faster than these software.
590 $a School code: 0227.
650 4 $a Biology, Bioinformatics. $3 1018415
650 4 $a Computer Science. $3 626642
690 $a 0715
690 $a 0984
710 2 $a The University of Texas at Austin. $b Computer Sciences. $3 1037904
773 0 $t Dissertation Abstracts International $g 68-07B.
790 $a 0227
790 1 0 $a Ramachandran, Vijaya, $e advisor
791 $a Ph.D.
792 $a 2007
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3274775