3
kruskal의 알고리즘을 병렬 처리해야하는데, 직렬 버전에서는 무차별 그래프에서 순환을 찾는 알고리즘을 사용했습니다. 이 코드 부분을 병렬 처리하는 방법이 있습니까?병렬 유니온 찾기 알고리즘
A
답변
3
글쎄, 어느 정도 병렬화 될 수 있습니다. 다음과 같습니다 :
처음에는 모든 가장자리가 오름차순으로 정렬됩니다. main thread가 실제로 처음부터 각 가장자리를 스캔하고 현재 가장자리를 추가하는 것이주기를 형성하는지 여부를 결정합니다. 알고리즘을 병렬 처리하는 주요 목적은 이러한 검사를 병렬화하는 것입니다.
여기서 우리는 worker threads을 사용합니다. 각 스레드는 검사 할 에지 수를 지정받습니다. 각 스레드는 각 반복이 끝날 때마다 현재 표현과 순환을 형성하는지 검사합니다 (반복은 주 스레드가 새 가장자리를 추가한다는 것을 의미합니다). 주 스레드가 가장자리를 계속 추가함에 따라 일부 스레드는 특정 가장자리가 이미 현재 표현과 함께 순환을 형성하고 있음을 확인합니다.
이러한 가장자리는 discarded으로 표시됩니다. 주 스레드가 이러한 가장자리에 도달하면 아무 것도 확인하지 않고 다음 스레드로 넘어갑니다.
따라서 우리는 실제로 이러한 검사를 병렬로 수행했습니다. 즉, 알고리즘이 빠르게 실행되어 효율성이 향상됩니다.
실제로 위에서 설명한 동일한 아이디어를 사용하는 nice paper이 있습니다.
는편집 : 당신은 꽤 많은 우려 이상 - 모든 알고리즘의 실행 시간에 대한 경우
, 당신은 심지어 @ jarod42로 처음 병렬 정렬 알고리즘을 사용할 수 있습니다 제안.
+0
이 방법을 openMP와 함께 사용하면 편리합니까? 제 말은 스케쥴로 스레드를 관리하는 것이 어려워 보입니다. – Betelgeuse
+1
@Betelgeuse 스레드를 만들고 각 스레드에 특정 수의 에지를 지정하기 만하면됩니다. 할당의 한 가지 방법은 연속적입니다. 그리고 새로운 면모가 추가 된 후에 검토 할 것입니다. 스레드에 할당 된 모든 에지가 주 스레드에 의해 완전히 처리되면 해당 작업자 스레드를 종료하십시오. 나는 그것이 쉽다 고 생각한다! – nitish712
관련 문제
- 1. 유니온 찾기 알고리즘 구현
- 2. 유니온 찾기 파이썬에서 알고리즘 찾기
- 3. 구조체에서 이름이없는 유니온 찾기
- 4. 그래픽 알고리즘 유니온, 교차, 뺄셈
- 5. 병렬 알고리즘 설계
- 6. Boruvka 알고리즘 병렬 구현 CUDA
- 7. 최대 차이를 계산하기위한 병렬 알고리즘
- 8. 병렬 프로그램에 대한 요약 알고리즘
- 9. 병합 정렬을위한 PRAM (병렬) 알고리즘
- 10. 픽셀을 전달하는 대용량 병렬 알고리즘
- 11. DDoS 방지를위한 병렬 알고리즘 설계?
- 12. pi를 계산하는 병렬 알고리즘 구현
- 13. 최소 스패닝 트리 알고리즘 병렬
- 14. 유니온 B에서 k 번째로 작은 원소 찾기
- 15. 가계도 조상 찾기 알고리즘
- 16. Java Anagram 찾기 알고리즘
- 17. 찾기 알고리즘 클래스
- 18. 복잡한 뿌리 찾기 알고리즘
- 19. 피크 찾기 알고리즘 오류
- 20. 열차의 길 찾기 알고리즘
- 21. 조상 찾기 알고리즘
- 22. 체크섬을 생성하는 알고리즘 찾기
- 23. 지뢰 찾기 알고리즘
- 24. 길 찾기 알고리즘
- 25. 비동기 찾기 알고리즘 최적화
- 26. KMP 패턴 찾기 알고리즘
- 27. 브래킷 찾기 알고리즘 루아?
- 28. 리스트 찾기 알고리즘
- 29. 파일 수정시 알고리즘 찾기
- 30. 일치하는 문자열 찾기 알고리즘
좋은 질문입니다! 지금까지 시도한 코드를 보여줄 수 있습니까? –
[Disjoint-set_data_structure] (http://en.wikipedia.org/wiki/Disjoint-set_data_structure)의 모든 기능은 거의 일정한 시간 (그러나 초기화)에 있기 때문에. 이 함수들에 대해 병렬 처리를하는 것이 의미가 있는지 궁금합니다 ... 병렬 처리는 가장자리를 정렬 할 수 있습니다. – Jarod42