Go : параллельное выполнение

[Olej]

- сборка элементарная:

Выполнение очень интересное ... но начинаем смотреть с того, на скольких процессорах будет выполняться, т.е. на оборудование:

Код: Выделить всё

olej@R420:~/2022/Go/probes$ inxi -Cxxx
CPU:       Topology: 2x 10-Core model: Intel Xeon E5-2470 v2 bits: 64 type: MT MCP SMP arch: Ivy Bridge rev: 4 
           L2 cache: 50.0 MiB 
           flags: avx lm nx pae sse sse2 sse3 sse4_1 sse4_2 ssse3 vmx bogomips: 192042 
           Speed: 2976 MHz min/max: 1200/3200 MHz Core speeds (MHz): 1: 2962 2: 2861 3: 2805 4: 2800 5: 2830 6: 2800 7: 2800 
           8: 2844 9: 2800 10: 2800 11: 2802 12: 2800 13: 2964 14: 2937 15: 2803 16: 2801 17: 2801 18: 2799 19: 2838 20: 2802 
           21: 2801 22: 2846 23: 2801 24: 2861 25: 2892 26: 2800 27: 2806 28: 2800 29: 2800 30: 2800 31: 2799 32: 2800 
           33: 2800 34: 2800 35: 2963 36: 2861 37: 2800 38: 2801 39: 2806 40: 2808 

Это промышленный сервер - 2 процессора, по 10 ядер каждый, с гипертриэдингом считая (как это делает Linux) - 40 процессоров.

Код: Выделить всё

olej@R420:~/2022/Go/probes$ ./mlpar 3
число процессоров в системе: 40
число ветвей выполнения: 3
[1,7f9854ea4740]
[3,7f985144f700]
[2,7f9851c50700]
итоговое время выполнения: 1.000125367s

Код: Выделить всё

olej@R420:~/2022/Go/probes$ ./mlpar 5
число процессоров в системе: 40
число ветвей выполнения: 5
[5,7f237e5e4740]
[1,7f237b390700]
[3,7f2379b4d700]
[2,7f237ab8f700]
[4,7f237bb91700]
итоговое время выполнения: 1.000307862s

Код: Выделить всё

olej@R420:~/2022/Go/probes$ ./mlpar 10
число процессоров в системе: 40
число ветвей выполнения: 10
[10,7f8659e15700]
[4,7f86497fa700]
[1,7f864a7fc700]
[7,7f864affd700]
[5,7f8658e13700]
[6,7f8648ff9700]
[8,7f864b7fe700]
[2,7f8649ffb700]
[3,7f8659614700]
[9,7f865c868740]
итоговое время выполнения: 1.001736132s

Хорошо видно как чередуются pthread_t - каждая горутина выполняется в своём потоке.

[Olej]

Это промышленный сервер

А теперь:

Код: Выделить всё

olej@nvme:~/2022/Go$ inxi -Cxxx
CPU:       Topology: Dual Core model: Intel Celeron G3930 bits: 64 type: MCP arch: Kaby Lake rev: 9 L2 cache: 2048 KiB
           flags: lm nx pae sse sse2 sse3 sse4_1 sse4_2 ssse3 vmx bogomips: 11599
           Speed: 2900 MHz min/max: 800/2900 MHz Core speeds (MHz): 1: 2900 2: 2900

Это новый процессор младшей группы, без всякого гипертрединга, 2 ядра:

Код: Выделить всё

olej@nvme:~/2022/Go$ ./mlpar 2
число процессоров в системе: 2
число ветвей выполнения: 2
[2,7f37483a0700]
[1,7f374739e700]
итоговое время выполнения: 1.00724748s

Код: Выделить всё

olej@nvme:~/2022/Go$ ./mlpar 4
число процессоров в системе: 2
число ветвей выполнения: 4
[2,7fa50b55b700]
[4,7fa50b55b700]
[1,7fa50c55d700]
[3,7fa50b55b700]
итоговое время выполнения: 1.016100188s

Код: Выделить всё

olej@nvme:~/2022/Go$ ./mlpar 10
число процессоров в системе: 2
число ветвей выполнения: 10
[10,7fd1541c8740]
[6,7fd1541c8740]
[5,7fd1541c8740]
[4,7fd1541c8740]
[2,7fd1541c8740]
[1,7fd1541c8740]
[7,7fd1541c8740]
[3,7fd1541c8740]
[8,7fd14bfff700]
[9,7fd1541c8740]
итоговое время выполнения: 1.083363676s

И здесь практически все горутины выполняются на одном ядре ... на втором, очевидно распределена главная ветвь, находящаяся, вообще то говоря, в заблокированном состоянии.

[Olej]

Выполнение очень интересное

Но это не то, чего я хотел добиться от этого кода...
Характерно как это выполняется на ARM одноплатном микрокомпьютере Orange Pi One:

Код: Выделить всё

olej@orangepione:~$ inxi -Cxxx
CPU:       Topology: Quad Core model: ARMv7 v7l variant: cortex-a7 bits: 32 type: MCP arch: v7l rev: 5 
           features: Use -f option to see features bogomips: 0 
           Speed: 1008 MHz min/max: 480/1008 MHz Core speeds (MHz): 1: 1008 2: 1008 3: 1008 4: 1008 

Код: Выделить всё

olej@orangepione:~$ ./mlpar 9
число процессоров в системе: 4
число ветвей выполнения: 9
[1,a57ff450]
[9,a57ff450]
[6,b6f14d50]
[4,a61ff450]
[7,a61ff450]
[8,a57ff450]
[2,a61ff450]
[5,a4ffe450]
[3,b6f14d50]
итоговое время выполнения: 1.041200876s

Здесь все 9 горутин по 1 сек. на 4 потока укладываются в итоговое время 1 сек.
И это потому, полагаю, что во время выполнения системного вызова time.Now() позволяется горутине переключиться на следующую ветку.
Чтобы этого не было, нужно функцию в go func(n int) ... переделать так, чтобы она выполняла только активную циклическую работу (вычислительную, тупую) без системных вызовов Linux. Но это всё уже на завтра...

[Olej]

Модели параллелизма, как они исторически появлялись в практике (это к процессу написания книги Книга: "Linux: многопроцессорная эффективность. Выбираем Go"):

1. Параллельные процессы, fork() ...

Концепция ветвления процессов впервые описана в 1962 году Мелвином Конвеем, а к 1964 году относятся первые реализации, которые были заимствованы Томпсоном при реализации операционной системы UNIX, и позже была включена в стандарты POSIX как обязательное требование для систем этого класса совместимости.

(сам себя цитирую )

2. Потоки ядра Linux, pthread_t ...

... только с 2003 года популярность потоков радикально возросла, когда стало понятно, что дальнейший рост производительности будет происходить не за счёт частоты процессора, а за счёт числа ядер процессора (или числа процессоров в системе).

3. Сопрограммы — модель Go ... Легкая модель, когда управления параллельными ветвями происходит без участия ядра операционной системы.

Интересный вопрос:
Насколько быстро происходит создание-активация параллельной ветви в каждой из моделей?

P.S. Собственно, 2 вопроса ... ещё так:
Насколько быстро (сравнительно) происходит взаимное переключение каждой из моделей в ходе выполнения?

[Olej]

Насколько быстро происходит создание-активация параллельной ветви в каждой из моделей?

Только в обратном порядке - начну с Go:
- gotim1.go :

Код: Выделить всё

package main
import ("os"; "strconv"; "fmt"; "time")

func sequgo(n int, c chan bool) {
	if n == 0 {
		c <- true
	} else {
		go sequgo(n - 1, c)
		<-c
	}
}

func main() {
	n := 1000
	if len(os.Args) > 1 {
		n, _ = strconv.Atoi(os.Args[1])
	}
	c := make(chan bool)
	t0 := time.Now()
	sequgo(n, c)
	fmt.Printf("[%d] время выполнения: %v\n", n, time.Now().Sub(t0))
}

Здесь N параллельных go-рутин (N можно указать параметром команды запуска) запускают друг-друга рекурсивно, по цепочке, и каждая k-я go-рутина, запускающая (k+1)-ю — ожидает её завершения. Активировавшись все N ветвей, они начинают так же, по цепочке, в обратном порядке завершаться.

Можно сделать проще (но как мне кажется, не настолько корректно) — запускать все требуемые N go-рутин из главной программы (одна за одной), и они завершаются сразу после запуска, но главная программа ожидает завершения всех N запущенных ветвей:
- gotim2.go :

Код: Выделить всё

package main
import ("os"; "strconv"; "fmt"; "time")

func main() {
	n := 1000
	if len(os.Args) > 1 {
		n, _ = strconv.Atoi(os.Args[1])
	}
	c := make(chan bool)
	t0 := time.Now()
	for i := 0; i < n; i++ {
		go func() { c <- true }()
	}
	for i := 0; i < n; i++ { <-c }
	fmt.Printf("[%d] время выполнения: %v\n", n, time.Now().Sub(t0))
}

[Olej]

Можно сделать проще (но как мне кажется, не настолько корректно) — запускать все требуемые N go-рутин из главной программы (одна за одной), и они завершаются сразу после запуска, но главная программа ожидает завершения всех N запущенных ветвей:

По такому же типу (это чуть менее корректно, но проще реализовать):
- thretim.c :

Код: Выделить всё

#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>
#include <pthread.h> 

void* tfunc(void* data) {
   pthread_exit(NULL);
}

int main(int argc, char *argv[]) {
   ulong n = argc > 1 ? atol(argv[1]) : 1000;
   pthread_t tid[n]; 
   struct timeval t0, t1;
   gettimeofday(&t0, NULL);
   for(int i = 0; i < n; i++)
      pthread_create(tid + i, NULL, tfunc, NULL); 
   for(int i = 0; i < n; i++) 
      pthread_join(tid[i], NULL);       

   gettimeofday(&t1, NULL);
   double t = (t1.tv_usec - t0.tv_usec) + (t1.tv_sec - t0.tv_sec) * 1000000;
   if(t < 1000)
      printf("время выполнения: %.3fµs\n", t);
   else
      printf("[%ld] время выполнения: %.3fms\n", n, t / 1000.);
   return 0;
}

- forktim.c :

Код: Выделить всё

#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <sys/wait.h>
#include <sys/time.h>

int main(int argc, char *argv[]) {
   ulong n = argc > 1 ? atol(argv[1]) : 1000;
   pid_t pid[n];
   struct timeval t0, t1;
   gettimeofday(&t0, NULL);
   for(int i = 0; i < n; i++)
      if((pid[i] = fork()) !=0)
         continue;
      else
         return 0;
   for(int i = 0; i < n; i++)
      waitpid(pid[i], NULL, 0);
   gettimeofday(&t1, NULL);
   double t = (t1.tv_usec - t0.tv_usec) + (t1.tv_sec - t0.tv_sec) * 1000000;
   if(t < 1000)
      printf("время выполнения: %.3fµs\n", t);
   else
      printf("[%ld] время выполнения: %.3fms\n", n, t / 1000.);
   return 0;
}

[Olej]

По такому же типу (это чуть менее корректно, но проще реализовать):

Код: Выделить всё

$ make
go build -o gotim1 -compiler gc gotim1.go
go build -o gotim2 -compiler gc gotim2.go
gcc -Wall forktim.c -lpthread  -o forktim
gcc -Wall thretim.c -lpthread  -o thretim

Код: Выделить всё

$ ./gotim1
[1000] время выполнения: 2.364592ms

$ ./gotim2
[1000] время выполнения: 2.689867ms

$ ./forktim
[1000] время выполнения: 59.344ms

$ ./thretim 
[1000] время выполнения: 36.257ms

Код: Выделить всё

$ ./gotim1 10
[10] время выполнения: 66.441µs

$ ./gotim2 10
[10] время выполнения: 114.853µs

$ ./forktim 10
время выполнения: 670.000µs

$ ./thretim 10
время выполнения: 508.000µs

Код: Выделить всё

$ ./gotim1 10000
[10000] время выполнения: 24.849198ms

$ ./gotim2 10000
[10000] время выполнения: 28.417926ms
$ ./thretim 10000
[10000] время выполнения: 354.031ms

$ ./forktim 10000
[10000] время выполнения: 625.808ms

Почувствуйте разницу!

[Olej]

Почувствуйте разницу!

При существенно больших значениях N (100000 и далее, в зависимости от ресурсов конкретного компьютера) варианты и для fork() и для pthread_create() сходят с ума, а компьютер в целом ведёт себя загадочным образом… вплоть до неустойчивости операционной системы, потому что это механизмы ядра системы.
(Но по своему опыту прежних лет знаю, что число созданных потоков ядра pthread_t параметризуется, может быть изменён, и число легко может быть несколько тысяч)

Но … наблюдаем сюда:

Код: Выделить всё

$ ./gotim1 1000000
[1000000] время выполнения: 2.242563217s

$ ./gotim2 1000000
[1000000] время выполнения: 5.352434703s

$ ./gotim1 10000000
[10000000] время выполнения: 22.5808485s

$ ./gotim2 10000000
[10000000] время выполнения: 53.33367164s 

10 миллионов параллельных ветвей (сопрограмм)?
Легко

[Olej]

Много интересного материала по теме...
Но я не успеваю сюда выкладывать.
Всё интересное, сразу по его появлению, см. в этом тексте: Книга: "Linux: многопроцессорная эффективность. Выбираем Go"

[Olej]

Очень новая книга: Is Parallel Programming Hard, And, If So, What Can You Do About It? (разные форматы)
PDF можно сразу читать или скачать здесь: Is Parallel Programming Hard, And, If So, What Can You Do About It?

Is Parallel Programming Hard, And, If So,
What Can You Do About It?
Edited by:
Paul E. McKenney
Facebook
paulmck@kernel.org
December 22, 2021
Release v2021.12.22a

930 стр.
Если кто интересуется тематикой - я советовал бы сохранить сразу сейчас.