Многопоточное сложение элементов массива

@XlorD59 · Регистрация: 28.05.2013

Студворк — интернет-сервис помощи студентам

Здравствуйте.

Задание - сложить многопоточно элементы одномерного массива.
На вход подаётся кол-во элементов и кол-во потоков.

Как это реализовать?

Мне понятно как создать нужное кол-во потоков. Т.е. это приблизительно выглядит так:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Program
    {
        static void Main(string[] args)
        {
            for (int i = 0; i < 10; ++i)
            {
                Thread thread = new Thread(ThreadFunction);
                thread.Start();
                Console.WriteLine("Поток "+i);
            }
            Console.Read();
        }
 
        static void ThreadFunction()
        {
            Console.WriteLine("");
        }
    }

Такая программа создаст соответственно 10 потоков, выведет в консоль их номера.

А вот как обрабатывать сложение элементов массива?
Для каждого потока писать отдельную функцию? Но на вход подаётся случайное кол-во потоков, как тогда нужное кол-во функций создать?

По сути, результат сложения будет в виде бинарного дерева, как я понимаю. (Извиняюсь, как картинку вставить я так и не понял, поэтому ссылка)

Т.е. на первом уровне происходит попарное суммирование элементов, на втором - суммирование получившихся сумм и так далее до ответа.

Подскажите пожалуйста, как вообще правильно разбивать элементы массива по разным потокам и передавать результат вычисления дальше, в эти же потоки?

@diagon · 05.06.2013, 21:31

m0nax, ну, это совсем не читерство, а единственно эффективный вариант распараллеливания в данной ситуации. Собственно, LINQ использует его же (причем как-то очень эффективно).
С вашим кодом получилось так

Code
1
2
3
4
5
6
7
8
9
10
ForSum: 8621 ticks
ForeachSum: 8709 ticks
ForEachSum: 39214 ticks
ParallelForEachSum: 320437 ticks
LinqSum: 101932 ticks
ParallelLinqSum: 16633 ticks
ManualParallelSum: 2601 ticks
CppSum: 3427 ticks
CppOmpSum: 3413 ticks
CppParallelSum: 1086 ticks

Сообщение от Psilon

diagon, сделай массив байтов длинной int.MaxValue/3 (чтобы не вылетело OutOfMemory) и затести на нем.

Придется исключить последовательный LINQ и Parallel.ForEach, иначе не дождусь.
Ну и 100 раз прогонять не обязательно, первые запуски нужны для того, чтобы процессор успел разогнаться до максимальной частоты. Для таких больших массивов хватит 10 раз.

P.S. если кому-то понадобится, прикрепил дллку (ее нужно распаковать и положить рядом с exe'шником). Примечание - она использует sse4.2 и скомпилирована под х64, так что на старых компьютерах может не пойти(кинет SEHExcetion).

Psilon · 05.06.2013, 22:08

Забавно, что небезопасный код в шарпе медленнее, чем обычный фор или форич...

Алсо, при попытке использовать ваш код вылетает:

System.BadImageFormatException
{"Была сделана попытка загрузить программу, имеющую неверный формат. (Исключение из HRESULT: 0x8007000B)"}

Psilon · 05.06.2013, 22:16

Алсо ради интереса:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
using System;
using System.Diagnostics;
using System.Linq;
using System.Runtime;
using System.Runtime.CompilerServices;
 
namespace ConsoleApplication36
{
    class Program
    {
        static unsafe void Main()
        {
            const int n = 10050*6;
            var a = stackalloc int[n];
            for (int i = 0; i < n; i++)
                a[i] = 6;
            DisableGC();
            GC.Collect();
            GC.WaitForPendingFinalizers();
            GC.Collect();
 
            var arr = Enumerable.Repeat(6, 10050 * 6).ToArray();
 
 
            var sw = new Stopwatch();
            sw.Start();
            int sum = StackallocTest(a, n);
            sw.Stop();
 
 
            GC.Collect();
            GC.WaitForPendingFinalizers();
            GC.Collect();
 
            var sw2 = new Stopwatch();
            sw2.Start();
            int sum2 = ForeachSum(arr);
            sw.Stop();
 
            
            Console.WriteLine("{0}\t{1}\tTime = {2}", "Stackalloc", sum, sw.ElapsedTicks);
            Console.WriteLine("{0}\t\t{1}\tTime = {2}", "Native", sum2, sw2.ElapsedTicks);
            Console.WriteLine("Stackalloc faster in {0} times", sw2.ElapsedTicks/(double) sw.ElapsedTicks);
            Console.ReadKey();
        }
 
        private static unsafe int StackallocTest(int* a, int n)
        {
            int sum = 0;
            for (int i = 0; i < n; i++)
                sum += a[i];
            return sum;
        }
 
        static int ForeachSum(int[] arr)
        {
            int res = 0;
 
            foreach (var x in arr)
            {
                res += x;
            }
 
            return res;
        }
 
        static void DisableGC()
        {
            GCLatencyMode oldMode = GCSettings.LatencyMode;
 
            // Make sure we can always go to the catch block, 
            // so we can set the latency mode back to `oldMode`
            RuntimeHelpers.PrepareConstrainedRegions();
 
            GCSettings.LatencyMode = GCLatencyMode.LowLatency;
        }
    }
}

Многопоточное сложение элементов массива

для исходной задачи получаем 1977 тиков. То есть даже быстрее, чем на С++. Единственный минус то, что объем хранимых данных ограничен размером стека.

@diagon · 05.06.2013, 22:24

Сообщение от Psilon

Забавно, что небезопасный код в шарпе медленнее, чем обычный фор или форич...

Разве? Обычный фор/форич работают в ~2.5 раза медленее обычного плюсового фора (ну, не совсем обычного, векторизированного :) )

Сообщение от Psilon

System.BadImageFormatException
{"Была сделана попытка загрузить программу, имеющую неверный формат. (Исключение из HRESULT: 0x8007000B)"}

Наверное, у вас ось/приложение 32битное. Хорошо, вот вариант под 32 бита, практически не использующий SSE. Правда, с такой библиотекой результаты достаточно скромные (т.к. без SSE оптимизировать там практически нечего(если особо не стараться :) ) ).

Code
1
2
3
4
5
6
7
8
9
10
ForSum: 6826 ticks
ForeachSum: 6814 ticks
ForEachSum: 35289 ticks
ParallelForEachSum: 252977 ticks
LinqSum: 78802 ticks
ParallelLinqSum: 18466 ticks
ManualParallelSum: 4490 ticks
CppSum: 6681 ticks
CppOmpSum: 6714 ticks
CppParallelSum: 2110 ticks

Psilon · 05.06.2013, 22:58

diagon, забавно, у меня шарп получается на порядок быстрее, чем параллельный С++

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
using System;
using System.Diagnostics;
using System.Linq;
using System.Runtime;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
 
namespace ConsoleApplication36
{
    class Program
    {
        static unsafe void Main()
        {
            const int n = 10050*6;
            var a = stackalloc int[n];
            for (int i = 0; i < n; i++)
                a[i] = 6;
            DisableGC();
            GC.Collect();
            GC.WaitForPendingFinalizers();
            GC.Collect();
 
 
            var sw = new Stopwatch();
            sw.Start();
            int sum = StackallocTest(a, n);
            sw.Stop();
 
 
            GC.Collect();
            GC.WaitForPendingFinalizers();
            GC.Collect();
 
            var sw2 = new Stopwatch();
            sw2.Start();
            int sum2 = NativeSum(a, n);
            sw2.Stop();
 
            GC.Collect();
            GC.WaitForPendingFinalizers();
            GC.Collect();
 
            var sw3 = new Stopwatch();
            sw3.Start();
            int sum3 = NativeParallelSum(a, n);
            sw3.Stop();
 
            
            Console.WriteLine("{0}\t{1}\tTime = {2}", "Stackalloc", sum, sw.ElapsedTicks);
            Console.WriteLine("{0}\t\t{1}\tTime = {2}", "Native", sum2, sw2.ElapsedTicks);
            Console.WriteLine("{0}\t{1}\tTime = {2}", "Native Parallel", sum3, sw3.ElapsedTicks);
            Console.WriteLine("Stackalloc faster in {0} times", sw2.ElapsedTicks/(double) sw.ElapsedTicks);
            Console.ReadKey();
        }
 
        private static unsafe int StackallocTest(int* a, int n)
        {
            int sum = 0;
            for (int i = 0; i < n; i++)
                sum += a[i];
            return sum;
        }
 
        static void DisableGC()
        {
            GCLatencyMode oldMode = GCSettings.LatencyMode;
 
            // Make sure we can always go to the catch block, 
            // so we can set the latency mode back to `oldMode`
            RuntimeHelpers.PrepareConstrainedRegions();
 
            GCSettings.LatencyMode = GCLatencyMode.LowLatency;
        }
 
        [DllImport("libcpp.dll", EntryPoint = "NativeSum")]
        private static extern unsafe int NativeSum(int* arr, int size);
 
        [DllImport("libcpp.dll", EntryPoint = "NativeOmpSum")]
        private static extern unsafe int NativeOmpSum(int* arr, int size);
 
        [DllImport("libcpp.dll", EntryPoint = "NativeParallelSum")]
        private static extern unsafe int NativeParallelSum(int* arr, int size);
    }
}

@diagon · 05.06.2013, 23:26

Psilon, PInvoke имеет достаточно большой оверхед на свой вызов. Поэтому (и не только) в моем бенчмарке берется минимум. Например, если занести обычный нативный for в цикл, (т.е. как-то так)

C#
1
2
3
4
5
6
7
8
9
            for (int i = 0; i < 20; ++i)
            {
                var sw2 = new Stopwatch();
                sw2.Start();
                int sum2 = NativeSum(a, n);
                sw2.Stop();
 
                Console.WriteLine(sw2.ElapsedTicks);
            }

То можно увидеть следующую картину

То есть самый первый вызов был очень тормознутым за счет подгрузки дллки, остальные пошли с заметно большей скоростью.

Psilon · 06.06.2013, 00:20

diagon, заинтересовало настолько, что полез в IL код смотреть... В итоге искорячил до исключения

Хотя программа на 4 строчки, из которых 2 - инициализация и reurn result

Криворукий ппц

Новые блоги и статьи Все статьи Все блоги /
Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .	Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .	Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .
Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм anaschu 30.08.2026 Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .	Оттачиваю умение писать js программы. russiannick 30.08.2026 Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман. Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .	мат медиц модель 30. презентация проекта anaschu 27.08.2026 хоп хоп хоп хидахоп, а я кладую))	Как у меня протекала болезнь zorxor 27.08.2026 Здравствуйте, друзья! Эта запись блога предназначена именно для вас - для моих дорогих друзей, которые знали меня лично. Чтобы ответить на вопрос - а что же со мной произошло на самом деле? Я учился. . .

Psilon Master of Orion 6102 / 4958 / 905 Регистрация: 10.07.2011 Сообщений: 14,522 Записей в блоге: 5
	06.06.2013, 00:20
	diagon, заинтересовало настолько, что полез в IL код смотреть... В итоге искорячил до исключения Хотя программа на 4 строчки, из которых 2 - инициализация и reurn result Криворукий ппц 0