이전에 방문한 노드로 한 프로세스를 이동하지 않고 2 또는 n 프로세스를 사용하여 그래프를 병렬로 탐색 할 수있는 알고리즘을 찾기 위해 인터넷에서 검색 중입니다. 그래서 그래프 전체의 스캐닝 작업 속도를 높일 수는 있지만, 아무것도 찾을 수 없습니다. 같은 작업을 병렬로 수행하는 데 도움이되는 알고리즘이 있습니까? 그만한 가치가 있니?2 또는 n 프로세스와 병렬로 그래프를 트래버스하는 방법
참고 : 시간의 대부분은 실제 탐색에 소요되는 경우를 제외하고 n 개의 프로세스가 방문 tovisit 노드
같은 메모리를 공유, 당신은 하나의 스레드에서 그래프를 통과 할 수있다, 당신당신은 그래프를 탐색하기위한 소비자 - 생산자 모델을 시도 할 수 있습니다 -하지만 순수 모델에서 일부 수정과 :
visited은 블록으로 설정됩니다. 동기화 시간을 절약 할 수 있습니다. 동기화 시간은 덜 자주 수행해야합니다.visited 집합)을 수정할 때 - 마지막으로 집합을 검사 한 이후 이미 방문한 데이터를 추가하지 않도록 추가 작업을해야합니다.이 방법을 사용하면 일부 정점을 몇 번 검색 할 가능성이 더 높아지지만 대기열 및 visited 세트가 업데이트되는 빈도로 바인딩 할 수 있습니다.
가치가 있습니까? 이러한 것들은 말하기 어렵습니다 - 많은 것들 (그래프 구조, 크기, 큐 구현, ...)에 의존합니다.
몇 가지 테스트를 실행하고 "얼마나 자주 업데이트해야합니까?"매개 변수를 미세 조정하여 경험적으로 더 나은지 확인하십시오. statistical tools (보통 wilcoxon test이 사실상 표준 임)을 사용하고 다른 하나가 더 나은지 판단해야합니다.
감사합니다 여러 프로세스에서 병렬로 처리 할 각 노드의 작업을 큐에 넣습니다. 대기열에서 작업 한 후 간단한 생산자 - 소비자 모델을 사용할 수 있습니다.
그래서 각 프로세스의 노드를 n 프로세스로 수집하는 작업을 분할하고 단일 프로세스가 방문 할 새 노드를 수집해야한다고 말합니까? – themis
이와 같은 모델은 그래프 탐색을 단순하게 유지하고 (현재 사용중인 알고리즘을 사용) 각 노드에서 수행되는 작업을 쉽게 병렬화 할 수 있습니다. –
또한 메모리 모델이 무엇인지 나타내야합니다. 공유 메모리입니까? – amit
예 공유 메모리입니다. – themis
이 사건은 생산자 소비자 문제처럼 보입니다. 그렇지만 프로세스가 서로 기다리면 가치가 있습니다. – themis