공식의 결과를 계산하는 가장 좋은 방법?

Question

현재 100 개의 사용자 정의 공식을 포함 할 수있는 응용 프로그램이 있습니다. 현재 리버스 광택 표기법을 사용하여 계산을 수행합니다 (값과 변수를 스택으로 푸시 한 다음 스택에서 팝업하여 평가). 이 과정을 병렬화하는 가장 좋은 방법은 무엇입니까? 기능적 언어를보고 있어야합니까?

계산은 숫자 배열에 대해 수행되므로 예를 들어 간단한 A+B는 실제로 100 개의 추가를 의미 할 수 있습니다. 저는 현재 델파이를 사용하고 있지만 이것은 앞으로 요구되는 요구 사항이 아닙니다. 작업에 가장 적합한 도구를 사용하겠습니다. 공식은 또한 서로에 의존 할 수 있으므로 예를 들어 하나의 공식 C = A+B이고 두 번째 공식 D = C+A가있을 수 있습니다.

Answer 1

당신의 공식 (방정식)이 주기적이지 않다고 가정 해 봅시다. 그렇지 않으면 "단지"평가할 수 없기 때문입니다. A = B + C와 같은 벡터화 된 방정식이있는 경우 A, B 및 C가 배열 인 경우 개념적으로 구성 요소의 방정식으로 분할하여 배열 크기가 5 인 경우이 방정식이 분할됩니다.

a1 = b1 + c1
a2 = b2 + c2
...
a5 = b5 + c5

이제 이것을 가정하면 간단한 수량 (정수, 합리적 또는 다른 것)에 대한 큰 방정식 세트가 있습니다.

두 방정식 E와 F가있는 경우 F의 오른쪽이 e의 왼쪽을 언급하는 경우 F의 부양 e라고 가정 해 봅시다.

E: a = b + c
F: q = 2*a + y

이제 이것을 계산하는 방법을 얻으려면 항상 무작위 반복을 사용 하여이 알고리즘에 따라 다음을 해결할 수 있습니다 (이것은 설명의 중간 단계 일뿐입니다).

1 while (there is at least one equation which has not been computed yet)
2   select one such pending equation E so that:
3     for every equation D such that E depends_on D:
4       D has been already computed
5   calculate the left-hand side of E

이 프로세스는 줄 // 2에서 선택한 방법에 관계없이 정답으로 종료됩니다. 이제 멋진 것은 쉽게 평행을 이루는 것입니다. 임의의 스레드 수로 실행할 수 있습니다! 당신이 필요로하는 것은 전제 조건 (방정식이 의존하는)이 계산되었지만 아직 스스로 계산되지 않은 방정식을 보유하는 동시성-안전 큐입니다. 모든 스레드가 한 번 에이 대기열에서 하나의 방정식이 튀어 나오고 답을 계산 한 다음 이제 새로운 방정식이 있는지 확인하여 모든 전제 조건이 계산되었는지 확인한 다음 해당 방정식을 추가합니다 (스레드-세일). 작업 대기열에. 완료.

Answer 2

더 많은 것을 알지 못하면 가능하면 SIMD 스타일 접근 방식을 취하는 것이 좋습니다. 즉, 단일 데이터 세트의 모든 공식을 계산하기위한 스레드를 작성하십시오. 공식의 계산을 병렬화하기 위해 공식의 계산을 나누려는 시도는 스레딩에 적합한 계산을 분리하기가 어렵고 올바르게 얻기가 어렵 기 때문에 계산을 분리하는 데 필요한 논리가 크게 향상되지 않습니다. 속도 이득이 없습니다. 또한 수익 감소로 빠르게 고통을 겪을 것입니다.

이제 많은 데이터 세트에 적용되는 공식 세트가 있다면 병렬화가 쉬워지고 더 잘 확장됩니다. 각 스레드는 하나의 데이터 세트에 대한 모든 계산을 수행합니다. CPU 코어 당 하나의 스레드를 생성하고 각 코어에 친화력을 설정하십시오. 각 스레드는 공식 평가 코드의 하나의 인스턴스를 인스턴스화합니다. 단일 데이터 세트를로드하고 유휴 스레드를 전달하는 감독자를 만듭니다. 스레드가 유휴 상태가없는 경우 첫 번째 스레드가 데이터 처리를 완료 할 때까지 기다리십시오. 모든 데이터 세트가 처리되고 모든 스레드가 완료되면 종료하십시오. 이 방법을 사용하면 스레드 스위칭이 느리고 전체 속도에 부정적인 영향을 미치기 때문에 CPU에 코어가있는 것보다 더 많은 스레드를 갖는 데 이점이 없습니다.

하나의 데이터 세트 만있는 경우 사소한 작업이 아닙니다. 다른 지점에 의존하지 않고 분기에 대한 평가 트리를 구문 분석하고 각 코어에서 실행되는 스레드를 분리하고 결과를 기다리기 위해 해당 지점을 농업해야합니다. 그런 다음 데이터를 동기화하고 데이터 일관성을 보장하는 문제가 발생합니다.