loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Fifth International Conference on Information Technology: New Generations (itng 2008)
A Coarse Grain Multicomputer Algorithm Solving the Optimal Binary Search Tree Problem
April 07-April 09
ISBN: 978-0-7695-3099-4
ASCII Text
x 
 
Mounir Kechid, Jean Fr?d?ric Myoupo, "A Coarse Grain Multicomputer Algorithm Solving the Optimal Binary Search Tree Problem," Information Technology: New Generations, Third International Conference on, pp. 1186-1189, Fifth International Conference on Information Technology: New Generations (itng 2008), 2008.
 
 
BibTex
x
 
@article{ 10.1109/ITNG.2008.158,
author = {Mounir Kechid and Jean Fr?d?ric Myoupo},
title = {A Coarse Grain Multicomputer Algorithm Solving the Optimal Binary Search Tree Problem},
journal ={Information Technology: New Generations, Third International Conference on},
volume = {0},
year = {2008},
isbn = {978-0-7695-3099-4},
pages = {1186-1189},
doi = {http://doi.ieeecomputersociety.org/10.1109/ITNG.2008.158},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Information Technology: New Generations, Third International Conference on
TI - A Coarse Grain Multicomputer Algorithm Solving the Optimal Binary Search Tree Problem
SN - 978-0-7695-3099-4
SP1186
EP1189
A1 - Mounir Kechid,
A1 - Jean Fr?d?ric Myoupo,
PY - 2008
KW - Dynamic programming
KW - Parallel algorithm
KW - CGM
KW - BSP
VL - 0
JA - Information Technology: New Generations, Third International Conference on
ER -
 
This paper presents a CGM parallel algorithm forthe cost of the Optimal Binary Search Tree Problem(OBST Problem). The best sequential algorithm forthis problem, due to Knuth, requires O(n2) time stepsand O(n2) space. Our CGM (Coarse GrainMulticomputer) algorithm uses p processors, each withO(n2/p) local memory. It requires O(p) communicationrounds and O(n2/p) local computations per processor.To the best of our knowledge, it is the first CGMparallel algorithm, based on the Knuth sequentialversion of the OBST problem.
Index Terms:
Dynamic programming, Parallel algorithm, CGM, BSP
Citation:
Mounir Kechid, Jean Fr?d?ric Myoupo, "A Coarse Grain Multicomputer Algorithm Solving the Optimal Binary Search Tree Problem," itng, pp.1186-1189, Fifth International Conference on Information Technology: New Generations (itng 2008), 2008
Usage of this product signifies your acceptance of the Terms of Use.