0

I currently have a shortest path algorithm that receives as inputs the Graph and a Node of origin, and returns the costs for all nodes in the graph plus the tree (precedents for each node). The graph is a dictionary, so are the costs AND the tree.

Since I have to compute the shortest path trees with origins in all nodes, it is only natural to do it in parallel (as the trees are independent of each other).

I'm doing it with the use of a pool of workers using the multiprocessing and appending the results to a list (so I want a list of dictionaries).

It runs without errors, but the interesting part is that the processing time does not change with the number of workers (NO CHANGE AT ALL).

Any insight on why does that happen will be mostly appreciated. Code follows below.

from LoadData import *
from ShortestPathTree import shortestPath
from time import clock, sleep
from multiprocessing import Pool, Process, cpu_count, Queue


def funcao(G,i):
    costs, pred=shortestPath(G,i)
    return pred


def main():

    #loads the graph
    graph="graph.graph"
    G = load_graph(graph)

    # loads the relevant nodes (CENTROIDS)
    destinations="destinations.graph"
    DEST = load_relevant_nodes(destinations)

    f = open('output_parallel.out','w')
    start=clock()


    pool=Pool()

    resultados=[]
    def adder(value):
        resultados.append(value)


    #for i in range(len(DEST)):
    for i in range(486):
        pool.apply_async(funcao, args=(G,DEST[i]), callback=adder)

    pool.close()
    pool.join()


    print clock()-start
    print >> f, resultados
    print >> f, 'seconds: '+ str(clock()-start)
4

1 回答 1

0

事实证明,@abarnert 在他询问每个电话需要多长时间时将其钉在了头上。输入的数据存在问题,使得每个呼叫都非常容易应答,因此为多个工作人员发送任务的开销补偿了性能的提高。

The results I get now that the input data was corrected are:

1核:185.0s 2核:111.2s 3核:96.6s 4核:87.5s

在双核超线程 i7 620M 联想 T410 笔记本电脑上运行(Win 7 64 位,Python 2.7.3)

感谢@abarnert 的伟大见解!

于 2012-11-09T20:01:07.867 回答