Turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

- Intel Community
- Software
- Software Development SDKs and Libraries
- Intel® oneAPI Threading Building Blocks
- Dijkstra's method whether it will give performance or not on intel tbb

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

sabbinenisunil

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

09-26-2010
08:11 AM

64 Views

Dijkstra's method whether it will give performance or not on intel tbb

Link Copied

7 Replies

Alexey_K_Intel3

Employee

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

09-30-2010
02:45 PM

64 Views

jimdempseyatthecove

Black Belt

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

09-30-2010
10:23 PM

64 Views

With Dijkstra's method you should be able to partition the verticies and work the partitions in parallel, with thread safe code to combine the results between partitions. As you read the n-Body exampleyou will find that your performance can very greatly if you can code to avoid interference between threads. (eliminate locks where they are not needed)

This sounds like this is an assignment.

Jim Dempsey

RafSchietekat

Black Belt

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

10-01-2010
11:37 AM

64 Views

Other than finding a solution somebody else has already provided (Alexey's suggestion is way too practical), I would first have a look at what A* says, and then try to devise something that doesn't depend on exact global aggregates. But I don't know if it will be better than Jim's intuition to first solve partitions, although I don't see how you could partition effectively without at the same time already solving the problem.

jimdempseyatthecove

Black Belt

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

10-01-2010
12:48 PM

64 Views

Look at the simplified case of N vertices 2 threads.

Divide N / 2 and have each thread solve the solution for each half. There may be an advantage to make the cut isolate nearby vertices (e.g. down the middle). Once each half has been solved, then each vertex need only to make a single probe to each of the other vertices (once) in the other zone. Meaning pick one zone, say zone A, divide vertices in two, have each thread process half the vertices of zone A with distance to all vertices in zone B. All the other paths (chains) have already been determined (weights may need to be adjusted). Extend the method to an arbitrary number of threads.

Effectively what you are doing is constructing chains or hyper threads within each zone by one thread per zone. Once those chains are constructed in each zone, the remaining task is to combine chains between zonesnot vertices. The work should be reduced. Taking care not to compare same chain pair or sequence more than once. As you combine chains, you may need only to check with chains whos ends are at/near the perimeter of the area with the chains at the perimeter of adjacent areas. e.g. look at chains of roads between Illinois and Missouri not Illinois and Massachusetts.

(pick your own adjacent states and disjointed states).

Jim Dempsey

RafSchietekat

Black Belt

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

10-03-2010
12:45 PM

64 Views

jimdempseyatthecove

Black Belt

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

10-05-2010
07:54 AM

64 Views

A determination has to be made as if you are to solve

a) the shortestpath between two specific points (specific solution)

b) the shortestpath between all points to all other points (general solution)

When performing a sieve operation to find a small number of items in a vast population most of the work is thrown away. Actually the "work" is discarding non-matching items. The trick is in reducing the amount of work and/or in distributing the work amongst multiple worker threads. Sometimes a "trick" can be employed for fast elimination of impossible routes. Most of the GPS solve for a), but route tables are solutions for b).

In a topology map (e.g. cities and roads), one might assume progression in the direction between the two points would yield the shortest or quickest path. This is not always the case. Sometimes going in the direction away from your destinationproduces ashorter path. Examples are where roads must cross bridges, and some times you must go away from your destination in order to cross a bridge leading to the shortest path. For these situations, the bridges represent choke points (as would sparse roads across wilderness).

Jim

RafSchietekat

Black Belt

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

10-05-2010
12:36 PM

64 Views

Regardless of topology, though, it should be possible to find the best route from New York to Newark without having to consider Forks, Washington (of Twilight fame), and I don't see a way to guarantee that without making the partitioning part of the search, not even considering cache locality. (Heuristics are fine if you can accept a possibly suboptimal solution, and once you have a route in euclidian space you can verify it by eliminating all points that are farther away in a direct line than the route already found, but perhaps that's not enough in a situation where you would want to resort to parallel searching.)

Topic Options

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Printer Friendly Page

For more complete information about compiler optimizations, see our Optimization Notice.