| Author | Urachart Kokaew |
| Call Number | AIT Thesis no. CS-96-26 |
| Subject(s) | Algorithms
|
| Note | A thesis submitted in partial fulfillment of the requirements for the degree of Mater of Engineering. |
| Publisher | Asian Institute of Technology |
| Series Statement | Thesis ; no. CS-96-26 |
| Abstract | Algorithms for irregular problems tend to be the most challenging to implement
efficiently on today's parallel machine because they differ markedly from the serial algorithms,
because they are often more complicated, requiring larger overheads, and also often require
more communication bandwidth than most current parallel machines can supply. This thesis
presents research work experience in parallel breadth-first-search algorithm, by applying
parallel algorithmic techniques to improve performance of an algorithm. The parallel breadthfirst-
search algorithms are implemented on the arbitrary concurrent write model in three
schemes. Implementations have been carried out in NESL :Nested-Data Parallel Language, a
data parallel language that supports nested data parallelism. As compared to most other parallel
languages, NESL puts greater emphasis on making codes, very high-level and concise. Their
running times are received and then compared to each scheme. The evaluation performance of
algorithms are considered as well. The result of divide-and-conquer with graph contraction
seems to be the best alternative because it can considerably reduce the size of a graph diameter,
since it is the most important factor in the algorithm. |
| Year | 1996 |
| Corresponding Series Added Entry | Asian Institute of Technology. Thesis ; no. CS-96-26 |
| Type | Thesis |
| School | School of Engineering and Technology (SET) |
| Department | Department of Information and Communications Technologies (DICT) |
| Academic Program/FoS | Computer Science (CS) |
| Chairperson(s) | Surapong C. |
| Examination Committee(s) | C., Yu;AS., Malik |
| Scholarship Donor(s) | Swedish International Development Agency. Government of Sweden |
| Degree | Thesis (M.Sc.) - Asian Institute of Technology, 1996 |