3
나는 alpha-beta 잘라내기를 추가로 구현 한 고전적인 미니 맥스 문제 해결사를 가지고 있습니다. 우리가 사용할 수있는 스레드 알파 - 베타가 암달의 법칙을 "깨뜨린"것입니까?
- 이 반복 심화를 수행 나는 다음과 같은 방법으로 알고리즘을 병렬화. 따라서 직렬 검색에서 깊이 2에서 가능한 9 개의 이동을 얻으면 먼저 4 개의 스레드를 시작한 다음 4 개의 스레드를 시작하고 마지막에 1을 시작합니다. 각 스레드는 깊이 2에서 시작하여 자체 매개 변수로 시작합니다.
4 스레드에 대한 S = T (직렬)/T (병렬)의 속도가 4.77이므로 Amdahl의 법칙을 근본적으로 위반하고 있습니다.
구현이 어떤 식 으로든 손상되지 않는다고 가정한다면 알파 베타 프 루닝이 여기서 마술을한다고 생각합니까? 여러 검색을 동시에 시작하기 때문에 더 많은 가지 치기가 있으며 일찍? 그것은 내 이론이지만 누군가가 이것을 더 자세히 확인할 수 있다면 좋을 것이다.
그냥 명확하게 :최소 최대를 알파 - 베타 구현은 기본적으로 약간의 최대 깊이까지 전체 트리의 깊이 우선 검색을하고하지 않고. 알파 베타를 사용하면 일부 분기를 잘라내어 어쨌든 더 나쁜 결과가 나오는 것을 제외하고는 동일하게 수행합니다.
편집 : 코드를 자세히 검토 한 후 프로그램을 "속이고"일부 동작을 따르지 않는 버그가있었습니다. 실제 가속 계수는 3.6입니다. 모든 사람의 시간을 낭비하게되어 죄송합니다. 오늘날 컴퓨팅 분야에서는 혁신이 없습니다. :/
하나의 스레드가 L3 캐시를 스파이크로 만들어 다른 코어가 메모리에보다 쉽게 액세스 할 수있게합니다. –