기억 저장소

프로젝트 투입 전, 동시성에 대한 복습이 필요했고 복습중 드는 의문들에 대한 테스트를 진행 해 보았다.

위 소스는 간단한 go routine을 사용한 예제 코드이며, 

Min은 int배열속의 최소값을 찾는 함수이며,

ParallelMin은 go routine(thread)를 이용하여 배열속 값들을 분배하여 동시에 최소값을 찾는 함수이다.

위 코드는 매우 가볍기 때문에 시간의 차이가 거의 나질 않아, Min함수에 Sleep 으로 100ms를 주어 약간의 가짜 부하를 주었다.

간단히 생각 해봤을 때, 당연히 쓰레드의 개수는 전체 수의 개수 n의 약수인것이 효율적이다.

그렇다면 가장 만만한 것은 n/2. (수의 크기는 100으로 주었다.)

우선 위 두개의 example 함수를 실행시켜 보자

훌륭하게도 시간이 거의 절반 가까이 줄었다.

하지만 이걸로는 부족하다.

위 쓰레드의 수는 임의의 값일 뿐이며, 효율적인 쓰레드의 개수는 아니다.

특히 위 함수의 경우에는 배열을 쓰레드들이 나누어 가져, MIn함수를 이용해 최소값들을 뱉어낸다.

그렇다면 1000개의 쓰레드를 돌리게 되면, 1000개의 최소값들이 나오고 결국 그 값들을 Min함수에 집어 넣는다면,

그 순간 부터만 n(n-1)/2의 처리, 즉 1000*999/2개의 처리가 다시 한번 소요된다.

그래서 위와 같은 계산 함수를 만들어 주었다.

Complexity는 수의 값을 비교하는 작업의 시간 복잡도를 계산하는 함수이며,

ThreadNum은 쓰레드 개수에 따른 쓰레드당 처리 크기를 계산해주는 함수이다.

크기가 111인 배열에 대한 복잡도들을 살펴보자.

복잡도 A는 쓰레드로 분할해 돌린 작업의 복잡도이며, B는 쓰레드들이 배출한 최소값들에 대한 작업의 복잡도이다.

@@ 쓰레드 개수 : 1, 트랜잭션 개수 : 111
복잡도 A : 6105
복잡도 B : 0
시간복잡도 : 6105.000000
@@ 쓰레드 개수 : 2, 트랜잭션 개수 : 111
복잡도 A : 1540
복잡도 B : 1
시간복잡도 : 1541.000000
@@ 쓰레드 개수 : 3, 트랜잭션 개수 : 111
복잡도 A : 666
복잡도 B : 3
시간복잡도 : 669.000000
@@ 쓰레드 개수 : 4, 트랜잭션 개수 : 111
복잡도 A : 378
복잡도 B : 6
시간복잡도 : 384.000000
@@ 쓰레드 개수 : 5, 트랜잭션 개수 : 111
복잡도 A : 253
복잡도 B : 10
시간복잡도 : 263.000000
@@ 쓰레드 개수 : 6, 트랜잭션 개수 : 111
복잡도 A : 171
복잡도 B : 15
시간복잡도 : 186.000000
@@ 쓰레드 개수 : 7, 트랜잭션 개수 : 111
복잡도 A : 120
복잡도 B : 21
시간복잡도 : 141.000000
@@ 쓰레드 개수 : 8, 트랜잭션 개수 : 111
복잡도 A : 91
복잡도 B : 28
시간복잡도 : 119.000000
@@ 쓰레드 개수 : 9, 트랜잭션 개수 : 111
복잡도 A : 78
복잡도 B : 36
시간복잡도 : 114.000000
@@ 쓰레드 개수 : 10, 트랜잭션 개수 : 111
복잡도 A : 66
복잡도 B : 45
시간복잡도 : 111.000000
@@ 쓰레드 개수 : 11, 트랜잭션 개수 : 111
복잡도 A : 55
복잡도 B : 55
시간복잡도 : 110.000000
@@ 쓰레드 개수 : 12, 트랜잭션 개수 : 111
복잡도 A : 45
복잡도 B : 66
시간복잡도 : 111.000000
@@ 쓰레드 개수 : 13, 트랜잭션 개수 : 111
복잡도 A : 36
복잡도 B : 78
시간복잡도 : 114.000000
@@ 쓰레드 개수 : 14, 트랜잭션 개수 : 111
복잡도 A : 28
복잡도 B : 91
시간복잡도 : 119.000000
@@ 쓰레드 개수 : 15, 트랜잭션 개수 : 111
복잡도 A : 28
복잡도 B : 105
시간복잡도 : 133.000000
@@ 쓰레드 개수 : 16, 트랜잭션 개수 : 111
복잡도 A : 21
복잡도 B : 120
시간복잡도 : 141.000000
@@ 쓰레드 개수 : 17, 트랜잭션 개수 : 111
복잡도 A : 21
복잡도 B : 136
시간복잡도 : 157.000000
@@ 쓰레드 개수 : 18, 트랜잭션 개수 : 111
복잡도 A : 21
복잡도 B : 153
시간복잡도 : 174.000000
@@ 쓰레드 개수 : 19, 트랜잭션 개수 : 111
복잡도 A : 15
복잡도 B : 171
시간복잡도 : 186.000000
@@ 쓰레드 개수 : 20, 트랜잭션 개수 : 111
복잡도 A : 15
복잡도 B : 190
시간복잡도 : 205.000000
@@ 쓰레드 개수 : 21, 트랜잭션 개수 : 111
복잡도 A : 15
복잡도 B : 210
시간복잡도 : 225.000000
@@ 쓰레드 개수 : 22, 트랜잭션 개수 : 111
복잡도 A : 15
복잡도 B : 231
시간복잡도 : 246.000000
@@ 쓰레드 개수 : 23, 트랜잭션 개수 : 111
복잡도 A : 10
복잡도 B : 253
시간복잡도 : 263.000000
@@ 쓰레드 개수 : 24, 트랜잭션 개수 : 111
복잡도 A : 10
복잡도 B : 276
시간복잡도 : 286.000000
@@ 쓰레드 개수 : 25, 트랜잭션 개수 : 111
복잡도 A : 10
복잡도 B : 300
시간복잡도 : 310.000000
@@ 쓰레드 개수 : 26, 트랜잭션 개수 : 111
복잡도 A : 10
복잡도 B : 325
시간복잡도 : 335.000000
@@ 쓰레드 개수 : 27, 트랜잭션 개수 : 111
복잡도 A : 10
복잡도 B : 351
시간복잡도 : 361.000000
@@ 쓰레드 개수 : 28, 트랜잭션 개수 : 111
복잡도 A : 6
복잡도 B : 378
시간복잡도 : 384.000000
@@ 쓰레드 개수 : 29, 트랜잭션 개수 : 111
복잡도 A : 6
복잡도 B : 406
시간복잡도 : 412.000000
@@ 쓰레드 개수 : 30, 트랜잭션 개수 : 111
복잡도 A : 6
복잡도 B : 435
시간복잡도 : 441.000000
@@ 쓰레드 개수 : 31, 트랜잭션 개수 : 111
복잡도 A : 6
복잡도 B : 465
시간복잡도 : 471.000000
@@ 쓰레드 개수 : 32, 트랜잭션 개수 : 111
복잡도 A : 6
복잡도 B : 496
시간복잡도 : 502.000000
@@ 쓰레드 개수 : 33, 트랜잭션 개수 : 111
복잡도 A : 6
복잡도 B : 528
시간복잡도 : 534.000000
@@ 쓰레드 개수 : 34, 트랜잭션 개수 : 111
복잡도 A : 6
복잡도 B : 561
시간복잡도 : 567.000000
@@ 쓰레드 개수 : 35, 트랜잭션 개수 : 111
복잡도 A : 6
복잡도 B : 595
시간복잡도 : 601.000000
@@ 쓰레드 개수 : 36, 트랜잭션 개수 : 111
복잡도 A : 6
복잡도 B : 630
시간복잡도 : 636.000000
@@ 쓰레드 개수 : 37, 트랜잭션 개수 : 111
복잡도 A : 3
복잡도 B : 666
시간복잡도 : 669.000000
@@ 쓰레드 개수 : 38, 트랜잭션 개수 : 111
복잡도 A : 3
복잡도 B : 703
시간복잡도 : 706.000000
@@ 쓰레드 개수 : 39, 트랜잭션 개수 : 111
복잡도 A : 3
복잡도 B : 741
시간복잡도 : 744.000000
@@ 쓰레드 개수 : 40, 트랜잭션 개수 : 111
복잡도 A : 3
복잡도 B : 780
시간복잡도 : 783.000000
@@ 쓰레드 개수 : 41, 트랜잭션 개수 : 111
복잡도 A : 3
복잡도 B : 820
시간복잡도 : 823.000000
@@ 쓰레드 개수 : 42, 트랜잭션 개수 : 111
복잡도 A : 3
복잡도 B : 861
시간복잡도 : 864.000000
@@ 쓰레드 개수 : 43, 트랜잭션 개수 : 111
복잡도 A : 3
복잡도 B : 903
시간복잡도 : 906.000000
@@ 쓰레드 개수 : 44, 트랜잭션 개수 : 111
복잡도 A : 3
복잡도 B : 946
시간복잡도 : 949.000000
@@ 쓰레드 개수 : 45, 트랜잭션 개수 : 111
복잡도 A : 3
복잡도 B : 990
시간복잡도 : 993.000000
@@ 쓰레드 개수 : 46, 트랜잭션 개수 : 111
복잡도 A : 3
복잡도 B : 1035
시간복잡도 : 1038.000000
@@ 쓰레드 개수 : 47, 트랜잭션 개수 : 111
복잡도 A : 3
복잡도 B : 1081
시간복잡도 : 1084.000000
@@ 쓰레드 개수 : 48, 트랜잭션 개수 : 111
복잡도 A : 3
복잡도 B : 1128
시간복잡도 : 1131.000000
@@ 쓰레드 개수 : 49, 트랜잭션 개수 : 111
복잡도 A : 3
복잡도 B : 1176
시간복잡도 : 1179.000000
@@ 쓰레드 개수 : 50, 트랜잭션 개수 : 111
복잡도 A : 3
복잡도 B : 1225
시간복잡도 : 1228.000000
@@ 쓰레드 개수 : 51, 트랜잭션 개수 : 111
복잡도 A : 3
복잡도 B : 1275
시간복잡도 : 1278.000000
@@ 쓰레드 개수 : 52, 트랜잭션 개수 : 111
복잡도 A : 3
복잡도 B : 1326
시간복잡도 : 1329.000000
@@ 쓰레드 개수 : 53, 트랜잭션 개수 : 111
복잡도 A : 3
복잡도 B : 1378
시간복잡도 : 1381.000000
@@ 쓰레드 개수 : 54, 트랜잭션 개수 : 111
복잡도 A : 3
복잡도 B : 1431
시간복잡도 : 1434.000000
@@ 쓰레드 개수 : 55, 트랜잭션 개수 : 111
복잡도 A : 3
복잡도 B : 1485
시간복잡도 : 1488.000000

위 Output들을 보면 전체 시간복잡도가 감소하다가, 쓰레드의 개수 11개를 기점으로 다시 늘어나는것을 볼 수 있다.

이는 복잡도 A의 감소폭이 복잡도 B의 증가폭에게 따라잡히며 발생하는 것으로, 이를 이용하면 효율적인 쓰레드의 수를 산정할 수 있을 듯하다.

다음과 같은 함수를 만들었고 이를 이용해 다시 한 번 프로그램을 돌려보았다.

1. 병렬없이 프로그램 실행 : 9.97s

2. 임의이 쓰레드 수를 적용한 프로그램 실행 : 5.03s

3. 최적의 쓰레드 수를 적용한 프로그램 실행 : 1.810s

아래는 노트에 먼저 끄적여본 식들.... 알아보기 힘들다. 좀 더 깔끔하게 쓰자!!

go routine을 공부하다 메모리를 분할해, 작업을 돌리는 간단한 예제를 작성 해 보았다.

크기가 x인 배열을 y개의 쓰레드로 분할하여 연산할때, 각 쓰레드의 사이즈를 할당하는 식을 구하는 문제이다.

[x/y] 는 x가 y의 배수일때만 사이즈가 적당하며 배수가 아닐 시엔 나머지가 버려진다. ( [ ]는 가우스 기호)

[x/y]+1 은 x가 y의 배수일 경우 몫이 항상 1개 더 남기에 비효율 적이다.

정답은 [x-1/y]+1 이다.

x가 y의 배수일 경우, x/y는 정수가되고 식은 [-1/y]+1가 가 되어 몫만 딱 남으며,

x가 y의 배수가 아닐 경우, x/y > n로 잡으면  x/y=n+R 이므로 n+[R-1/y]+1 = n+1+[R-1/y] 이고, R의 범위는 0/y<R<y/y이므로 n+1이 된다.

그러므로 배수일 경우 딱 맞게, 배수가 아닐 경우 여유를 주고 분할 할 수있다.

- 소스

func ParallelMin(a []int, n int) int {
	if len(a) < n {
		return Min(a)
	}
	mins := make([]int, n)
	size := (len(a) + n-1) / n
	var wg sync.WaitGroup
	for i := 0; i < n; i++ {
		wg.Add(1)
		go func(i int) {
			defer wg.Done()
			begin, end := i*size, (i+1)*size
			if end > len(a) {
				end = len(a)
			}
			mins[i] = Min(a[begin:end])
		}(i)
	}
	wg.Wait()
	return Min(mins)
}

아이패드에서 끄적인 증명 (애당초, 보여주려고 쓴건 아니라서 남이 보기는 어려울 수 있다.)