Search

'구간분할'에 해당되는 글 1건

  1. 2012.02.17 Welcome to Parallel C#(16) - 분배 전략. 1

Welcome to Parallel C#(16) - 분배 전략.

C# Parallel Programming 2012. 2. 17. 09:00 Posted by 알 수 없는 사용자
이번에는 TPL에서 제공하는 옵션에 대해서 알아보겠습니다. 병렬 작업을 위해서는 먼저 병렬로 수행할 수 있게끔 작업을 분할하는 일이 먼저 수행되어야 합니다. 예를 들어서 10000개의 데이터를 4개의 스레드가 나눠서 처리해야 하고, 각 10000개의 작업이 독립적이라면, 이걸 공평하게 4등분 할 것인지, 혹은 다른 방법을 사용할 것인지등을 결정하는 것 말이죠.


- 두 가지 선택.

TPL에서 작업 분할을 할때 사용하는 방법으로 구간 분할과 로드 밸런싱이 있습니다. 구간 분할을 루프의 크기를 스레드의 개수만큼 공평하게 나눠서 처리하는 것을 말합니다. 단순하죠.  :) 그리고 로드밸런싱은
처리할 구간을 미리 정하지 않고, 처리해야 할 작업에 따라서 각 스레드가 처리할 구간의 크기나 스레드의 개수가 유동적으로 변하게 됩니다. 이때 스레드하나가 이 작업을 담당하게 됩니다. 이 스레드는 작업 상황을 지켜보면서 그때 그때 스레드를 생성해서 작업을 맡기등의 역할을 맡게 되는 거죠. 그래서 작업을 끝낸 스레드가 다음에 처리할 구간을 할당받기 전까지 기다리는 시간이 필요하고, 이런 동기화에 따른 부하가 발생하게 되는 거죠. 나눠주는 구간의 크기가 작을 수록 스레드는 자주 구간을 할당받으려고 기다려야 하고 성능은 더 저하되는 거죠. :)

Parallel.For의 기본 동작은 로드 밸런싱을 사용하도록 되어 있습니다. 그래서 위에서 언급한 동기화 이슈가 자주 발생하는 경우 싱글스레드로 실행되는 for루프에 비해서 그다지 성능의 우위를 보이지 못하게 됩니다. 예제로 확인해볼까욤? ㅋㅋ

using System;

using System.Linq;

using System.Threading.Tasks;

using System.Collections.Concurrent;

using System.Collections.Generic;

 

namespace Exam20

{

    class Program

    {

        static void RangeParallelForEach(int[] nums)

        {

            List<int> threadIds = new List<int>();

            var part = Partitioner.Create(0, nums.Length);

 

            Parallel.ForEach(part, (num, state) =>

            {

                if (!threadIds.Contains(Task.CurrentId.Value))

                {

                    threadIds.Add(Task.CurrentId.Value);

                }

 

                for (int i = num.Item1; i < num.Item2; i++)

                {

                    nums[i] = nums[i] * nums[i];

                }

            });

 

            Console.WriteLine("Thread ID list of RangeForEach");

            foreach (var id in threadIds)

            {

                Console.WriteLine("{0}", id.ToString());

            }

        }

 

        static void ParallelFor(int[] nums)

        {

            List<int> threadIds = new List<int>();

 

            Parallel.For(0, nums.Length, (i) =>

            {

                if (!threadIds.Contains(Task.CurrentId.Value))

                {

                    threadIds.Add(Task.CurrentId.Value);

                }

 

                nums[i] = nums[i] * nums[i];

            });

 

            Console.WriteLine("Thread ID list of ParallelFor");

            foreach (var id in threadIds)

            {

                Console.WriteLine("{0}", id.ToString());

            }

        }

 

        static void Main(string[] args)

        {

            int max = 50000000;

            int[] nums1 = Enumerable.Range(1, max).ToArray<int>();

            int[] nums2 = Enumerable.Range(1, max).ToArray<int>();

 

            ParallelFor(nums1);

            RangeParallelForEach(nums2);

        }

    }

}

위 코드를 보면 로드밸런싱을 사용하는 Parallel.For와 Partitioner.Create 메서드를 이용해서 구간분할을 사용하도록 설정한 Parallel.ForEach를 사용하는 코드를 포함하고 있습니다. 이렇게 수행하면서 각 방법 별로 몇 개의 스레드가 생성되는지 확인한 결과를 볼까요.

Thread ID list of ParallelFor
1
2
3
4
5
6
7
8
9
10
--------------중략--------------
91
92
93
94
95
96
97
98
99
100
101
Thread ID list of RangeForEach
102
103
104
105
106
107
108
Press any key to continue . . .

구간 분할을 사용하는 경우(RangeForEach)는 고작 7개의 스레드가 생성되어서 작업을 처리한 것에 비해서, 로드밸런싱을 사용한 경우는 무려 101개의 스레드가 생성된 것을 볼 수 있습니다. 스레드가 많이 교체되면서 생기는 비효율성은 굳이 말을 안해도 되겠죵. 그렇다면 다음과 같은 코드로 실제로 어떤 속도의 차이가 발생하는지 확인을 해보시져 :)

using System;

using System.Linq;

using System.Threading.Tasks;

using System.Collections.Concurrent;

 

namespace Exam21

{

    class Program

    {

        static void NormalFor(int[] nums)

        {

            for (int i = 0; i < nums.Length; i++)

            {

                nums[i] = nums[i] * nums[i];

            }

        }

 

        static void ParallelFor(int[] nums)

        {

            Parallel.For(0, nums.Length, (i) =>

            {

                nums[i] = nums[i] * nums[i];

            });

        }

 

        static void RangeParallelForEach(int[] nums)

        {

            var part = Partitioner.Create(0, nums.Length);

 

            Parallel.ForEach(part, (num, state) =>

            {

                for (int i = num.Item1; i < num.Item2; i++)

                {

                    nums[i] = nums[i] * nums[i];

                }

            });

        }

 

        static void Main(string[] args)

        {

            int max = 50000000;

            int[] nums1 = Enumerable.Range(1, 10).ToArray<int>();

            int[] nums2 = Enumerable.Range(1, 10).ToArray<int>();

            int[] nums3 = Enumerable.Range(1, 10).ToArray<int>();

 

            //JIT컴파일을 위해.

            NormalFor(nums1);

            ParallelFor(nums2);

            RangeParallelForEach(nums3);

 

            nums1 = Enumerable.Range(1, max).ToArray<int>();

            nums2 = Enumerable.Range(1, max).ToArray<int>();

            nums3 = Enumerable.Range(1, max).ToArray<int>();

 

            DateTime normalForStart = DateTime.Now;

            NormalFor(nums1);

            DateTime normalForEnd = DateTime.Now;

            TimeSpan normalForResult = normalForEnd - normalForStart;

 

            DateTime parallelForStart = DateTime.Now;

            ParallelFor(nums2);

            DateTime parallelForEnd = DateTime.Now;

            TimeSpan parallelForResult = parallelForEnd - parallelForStart;

 

            DateTime rangeForStart = DateTime.Now;

            RangeParallelForEach(nums3);

            DateTime rangeForEnd = DateTime.Now;

            TimeSpan rangeForResult = rangeForEnd - rangeForStart;

 

            Console.WriteLine("Single-threaded for : {0}", normalForResult);

            Console.WriteLine("Load-balancing Parallel.For : {0}", parallelForResult);

            Console.WriteLine("Range-partition Parallel.ForEach : {0}", rangeForResult);

        }

    }

}

좀 어글리한 코드이긴 하지만, 싱글 스레드를 사용한 for루프와 로드 밸런싱을 사용하는 Parallel.For, 그리고 구간 분할을 사용하도록 한 Parallel.ForEach의 성능을 각각 비교한 코드입니다. 그럼 결과를 확인해보죠!

Single-threaded for : 00:00:00.3000763
Load-balancing Parallel.For : 00:00:00.3430858
Range-partition Parallel.ForEach : 00:00:00.2130545
Press any key to continue . . .

조금은 의외의 결과가 나왔습니다. 오히려 병렬로 작업을 처리한 Parallel.For가 순차적으로 실행되는 for루프에 비해서 낮은 성능을 낸 것이죠. 왜 그럴까욤? 첫 번째 원인은 너무 빈번하게 스레드 간의 작업 전환을 하느라 오버헤드가 컸던 점을 들 수 있을 것 같구요. 그리고 다음은, 병렬 작업에 사용되는 델리게이트의 내용이 너무 짧아서 입니다. 위 코드를 보면 델리게이트의 내용이 간단한 연산 한 줄로 이루어진 것을 볼 수 있는데요. 위 처럼 호출 수가 작은 경우는 큰 문제가 되지 않지만, 위의 코드 처럼 많은 횟수를 호출하는 경우 델리게이트 호출은 부담이 됩니다. 델리게이트의 내용을 처리하는 것 보다 델리게이트를 호출하는 시간이 더 많이 걸리게 되면서 일반 for루프보다도 못한 성능을 보여주는 거죠. 그래서 Partitioner.Create메서드를 이용해서 큰 작업 덩어리로 잘라줘서 이 오버헤드를 줄일 수 있습니다. 그 결과 위와 같은 시간이 나오게 된거죠.

어떻나요? 단순히 for루프를 Parallel.For로 교체하는 것만 가지고는 제대로된 성능을 기대하기 힘듭니다. 혹시, "어? 뭐야 당신 이전 포스트에서는 단순히 Parallel.For를 쓰기만 해도 성능이 좋아진다며?" 하는 생각이 드셨다면... 당신은 저의 팬...???!?!? ㅋㅋㅋㅋ 아마 기억하시는 분은 없겠죠. 암튼, 주의하고 볼일 입니다. 오늘은 여기까징~! :)