Loading...
Search
| Friend's email | |
| Your name | |
| Your email | |
| enter code | |
This page was sent successfuly
Digital Object List
Bookmark
Review List
922 viewed
یافتن کوتاه ترین مسیر روی سطوح نامنظم مثلث بندی شده وزن دار به کمک الگوریتم های چندهسته ای
غیور باغبانی، فرزانه Ghayour Baghbani, Farzaneh
Computing the Shortest Path on Weighted Triangulated Irregular Networks by Multicore Algorithms
Ghayour Baghbani, Farzaneh | 2011
1888
Viewed
- Type of Document: M.Sc. Thesis
- Language: Farsi
- Document No: 42119 (19)
- University: Sharif University of Technology
- Department: Computer Engineering
- Advisor(s): Ghodsi, Mohammad
- Abstract:
- Shortest path computation is one the fundamental problems in computer science. Triangulated Irregular Networks (TINs) are used in computational geometry to represent terrians and geometric surfaces. One of the most efficient mothods to solve the shortest path problem on a TIN is reducing it to shortest path problem on a graph. This reduction from continuous space to discrete space results in approximate solutions, but acceptable in real applications. In real applications we still encounter a large graph and using the simple Dijkstra algorithm consumes a lot of times. Memory shortage is another issue. Parallel processing could be a solution in this case. Multicore industry caused a revoloution in parallel processing. Now we found multicore processors every where. But multicore processing is different from older distributed memory parallel system. Design and implementation of a efficient program for a multicore system needs much more effort. In this thesis we are trying to answer the shortest path queries on weighted TINs. On our approach we encounter single source shortest path problem on weighted graphs. We give a survey on sequential and parallel methods for speeding up shortest path queries on weighted graphs and suggest a new method based on shortcuts. The method is implemented by OpenMP and the experimental results on realistic data shows the efficiency of the algorithm
- Keywords:
- Shortest Path ; Multicore Processors ; Triangulated Irregular Network Terrian (TIN)
-
محتواي پايان نامه
- view
- فهرست
- فهرست تصاویر
- فهرست جداول
- مقدمه
- معرفی مساله کوتاهترین مسیر بر روی سطوح نامنظم مثلثبندیشده
- سطح نامنظم مثلثبندی شده
- مساله کوتاهترین مسیر و کارهای انجام شده
- کوتاهترین مسیر در نظریه گرافها
- کوتاهترین مسیر در هندسه محاسباتی
- الگوریتمهای ترتیبی کوتاهترین مسیر روی سطوح نامنظم مثلثبندی شده وزندار
- الگوریتم Mitchell و Papadimitriou
- گراف تقریب تین
- نقاط کمکی
- نقاط کمکی نمایی
- حالات خاص مساله با محدودیتهای بیشتر
- الگوریتمهای تسریع و موازیسازی یافتن کوتاهترین مسیر بر روی گرافها
- ناحیهبندی
- تقسیم قطاعی
- MFP
- PCD
- جداکنندهها
- سلسله مراتبی
- علامتگذاری یال
- مسیریابی بر مبنای دسترسی
- نگهدارنده هندسی
- جستوجوی دو طرفه
- جستوجو به سمت هدف
- روش رئوس مهم
- گام دلتا
- ناحیهبندی
- پردازش چندهستهای
- پردازندههای چندهستهای Intel
- Cell
- GPU
- کارهای انجام شده در مورد الگوریتمهای چندهستهای
- الگوريتم پيشنهادی
- نسخه اولیه
- پيادهسازی و ارزيابی
- دادههای ورودی
- پیاده سازی نسخه اولیه الگوریتم تسریع و پیادهسازی چندهستهای آن
- مقایسه با دیگر الگوریتمها و بهبود
- خلاصه و نتيجهگیری
- تینهای ورودی
- تصاویر خروجی
- کتابنامه
- واژهنامه فارسی به انگلیسی
- واژهنامه انگلیسی به فارسی