분산 그래프 알고리즘의 성능을 가속화하는 방법은 무엇입니까?

Question

다음과 같은 그래프 문제가 있으며 실행 시간 성능을 최적화해야합니다. 나는 단지 프로그래밍 기술 을 찾고 알고리즘 최적화가 아닌을 사용하여 성능을 향상시키고 자합니다. 문제는 다음과 같다 : 그래프 G (V, E)가 주어지면, 각 노드 u는 u의 모든 2 홉 이웃이 이웃이되도록 다중 집합 릴레이 (M_r (u))라고 불리는 이웃 N M_r (u)의 적어도 하나의 노드에 전달한다. 노드 u에서의 M_r (u)의 구성은 다음과 같다.

construct_mr(u) 
1) M_r(u) is initially empty. 
1') The set of non-covered 2-hop of neighbors of u is the set of all 2-hop neighbors of u. 
// a covered 2-hop neighbor of u: is a 2-hop neighbor of u that is also a neighbor to at least one of the nodes of M_r(u). 
2) while (M _r(u) is not a multiset relay set) 
2a) update the set of non-covered 2-hop neighbors of u. 
2b) add to M_r(u) a neighbor v that cover the most non-covered 2-hop neighbors of u. 

자, 내가 한 것은 다음이었다

for each node u \in V: construct_mr(u). 

가 직렬화 구현 및 그래프가 크고 밀도가 끔찍한 실행 시간이 본원 문제. Java 또는 C++를 사용하여 이러한 알고리즘의 성능을 가속화하는 방법을 찾고 있습니다. 하지만 멀티 스레딩에 대해서는 좋은 성능을 얻기 위해 스레드 스케줄링을 사용해야합니까? [메시지 전달 프로그래밍 모델은 아무런 메시지도 전달하지 않으므로 아무런 효과가 없습니다.]

Answer 1

분산 구현이 도움이 될지 의심 스럽습니다.

두 가지 홉 이웃을 각각 식별하는 그래프 트래버 설 프로세스가 문제의 핵심입니다. 각 인스턴스는 전체 그래프를 필요는 niave 경우

• :이 작업을 수행하기 위해, 알고리즘의 분산 버전의 인스턴스의 각 그래프의 사본이 필요합니다. 인스턴스에 그래프를 배포하는 데 걸리는 시간이 순전히 병렬 단계의 속도 향상을 초과한다는 것을 알 수 있습니다.

• 그래프를 분할하고 각 인스턴스를 그래프의 일부로 보내는 방법도 있습니다. 그러나 그래프의 일부가 아닌 그래프 노드를 찾기 위해 인스턴스가 다른 인스턴스와 대화하는 데 필요한 인스턴스가 생겼습니다. 그러면 아마 병렬 처리를 무효화 할 것입니다.

이 (엄지 손가락의 규칙으로 분산 솔루션을 사용하면 인스턴스 사이에 많은 데이터를 이동할 수없는 경우 가장 잘 작동하고, 계산은 주로 다른 사람에게 이야기하지 않고 인스턴스에 의해 수행 할 수 있습니다. 통신 비용 및 인스턴스 간 동기화는 병렬 처리를 중지시키는 경향이 있습니다.)

아니요. 병렬 처리하려는 경우 가장 좋은 방법은 단일 JVM에서 멀티 스레딩을 사용하는 것입니다. 주어진 알고리즘 구현에 대해 최상의 성능을 얻으려면 스레드 수를 사용 가능한 프로세서 수와 같게 설정하십시오. 그것보다 더 많은 스레드를 생성하면 상황이 나 빠지게됩니다. (그리고 그것은 도움이되지 않습니다 ... 스레드 스케줄링 바이올린하지 않습니다.)

---

내가 당신의 계산 속도가 느린 진짜 이유는 알고리즘과 방법의 세부 사항에 있음을 의심했다 가졌 당신은 데이터 구조를 구현했습니다.

저속 알고리즘을 빠르게 변경할 수있는 "프로그래밍 기술"은 없습니다 ... 변경하지 않고 말입니다.

(코드를 프로파일 링하고, 대부분의 시간이 소요되는 장소를 식별하고 ... 깊이 생각한 후 코드/데이터 구조를 재 설계하여 개선하십시오. 여기에는 어떤 마법도 없습니다. 열심히 일하고 생각하십시오.)