Shine A Light

Since the goal of Parallel Extensions is to simplify parallel programming, and the motivation behind parallel programming is performance, it is not surprising that many of the questions we receive about our CTP releases are performance-related.
: Parallel Extensions의 목표가 간단하게 Parallel Programming을 구현하는 것이라고 공개된 뒤 우리는 우리의 CTP에 Performance에 대한 많은 질문을 받았다.

Developers ask why one program shows a parallel speedup but another one does not, or how to modify a program so that it scales better on multi-core machines.
: 개발자들은 멀티코어 PC에 맞게 프로그램을 수정했는데, 몇몇 프로그램에서는 속도가 빨라지지 않는 것에 대해 문의했다.

The answers tend to vary. In some cases, the problem observed is a clear issue in our code base that is relatively easy to fix. In other cases, the problem is that Parallel Extension does not adapt well to a particular workload. This may be harder to fix on our side, but understanding real-world workloads is a first step to do that, so please continue to send us your feedback. In yet another class of issues, the problem is in the way the program uses Parallel Extensions, and there is little we can do on our side to resolve the issue.
: 대답은 다양하다. 어떠한 경우에는, 코드를 수정하기 쉬운 명확한 이유일 때도 있다. 다른 경우에서는 특정 작업에 Parallel Extension이 제대로 적용되지 않은 문제이기도 하다. 이것은 우리들도 고치기 힘들지도 모른다. 그러나 먼저 실제 작업에 대해 이해하는 것이 순서이므로 계속해서 우리와 질의자사이에 feedback을 주고 받아야 한다.

Interestingly, it turns out that there are common patterns that underlie most performance issues, regardless of whether the source of the problem is in our code or the user code. In this blog posting, we will walk though the common performance issues to take into consideration while developing applications using Parallel Extensions.
: 흥미롭게도, 대부분의 성능 이슈에 대해서 공통적인 패턴을 보이는데, 우리의 코드나, 유저의 코드에 대한 문제일수도 아닐수도 있다. 우리는 Parallel Extension을 사용하여 Application을 개발하는 데에 있어 고려해야 하는 공통적인 성능 이슈들에 대해서 말하겠다.

Amount of Parallelizable CPU-Bound Work 

The number one requirement for parallelization is that the program must have enough work that can be performed in parallel. If only half of the work can be parallelized, Amdahl’s Law dictates that we are not going to be able to speed up the program by more than a factor of two.
: Parallelization을 위한 가장 중요한 요구사항은 프로그램이 Parallel화 될 수 있는 작업이어야만 한다는 것이다. 만약 작업의 절반만 Parallel화 할 수 있다면, Amdahl's Law에 따라 우리는 프로그램의 속도를 향상시킬 수 없다.

Also, additional CPUs thrown at a task will help the most if the CPU was the performance bottleneck. If the program spends 90% of its time waiting for a server to execute SQL queries, then parallelizing the program likely will not achieve significant benefits. (Well, you may still observe a speedup if there are multiple requests that we can send, say to multiple servers. In such cases, though, the asynchronous programming model would likely result in even better performance.)
: 또한, 추가적으로 CPU들에게 작업을 할당하는 것은 CPU성능에 있어서 병목현상을 발생 시킬 수도 있다. 만약 SQL 쿼리를 서버에서 실행하기 위해 프로그램의 수행시간의 90%를 사용한다면, Parallelizing하는 것은 크게 효과를 보일 수 없다.(아마 너는 여러개의 request들을 보내면 성능이 향상될지도 모른다 하겠지만, 이것은 여러개의 서버가 필요한 문제다. 몇몇 경우에서는 비동기 프로그래밍 모델이 더 나은 성능을 보여주기도 한다)

To benefit from parallelism, the total amount of processor-intensive work in a program must be large enough to dwarf the overheads of parallelization, and a large fraction of that work must be decomposable to run in parallel.
: Parallelism을 통해 효과를 얻으려면, Processor-intensive작업의 전체 양이 병렬화의 overhead가 충분히 커야 하고 그리고 작업이 큰 단위로 나누어 질 수 있어야만 한다.

Task Granularity

Even if a program does a lot of parallelizable work, we must be careful to ensure that we will split up the work into appropriately-sized chunks which will execute in parallel. If we create too many chunks, the overheads of managing and scheduling the chunks will be large. If we create too few chunks, some cores on the machine will have nothing to do.
: 프로그램이 많은 부분이 병렬화 작업이더라도, 우리는 Parallel로 수행하기 위해 작업을 적절한 크기의 chunk들로 쪼개는 것에 대해 주의해야 한다. 만약 우리가 너무 많은 chunk들을 생성하면, chunk의 관리와 스케쥴링의 overhead가 커지게 된다. 만약 너무 적은 chunk들을 생성했다면, 몇몇 core들은 아무 작업도 하지 않게 될 것이다.

In some parts of the Parallel Extensions API, such as Parallel.For and PLINQ, the code in our library is responsible for deciding on the proper granularity of tasks. In other parts of the API, such as tasks and futures, it is the responsibility of the user code. Regardless of who is responsible for creating the tasks, appropriate task granularity is important in order to achieve good performance.
: Parallel.For와 PLINQ와 같은 Parallel Extension API의 일부분은, Library안의 코드는 작업의 Proper granularity를 결정하는 것을 담당한다. Tasks와 futures와 같은 API의 다른 부분에서는 유저 코드에 대한 것을 담당한다. tasks 생성하는 것을 담당하고 있어도, 좋은 성능을 내기 위해 적합한 task granularity를 결정하는 것은 중요하다.

Load Balancing

Even if there is enough parallelizable CPU work to make parallelism worthwhile, we need to ensure that the work will be evenly distributed among cores on the machine. This is complicated by the fact that different “chunks” of work may differ widely in the time required to execute them. Also, we often don’t know how much work each chunk will require until we execute it till completion.
: 만약 충분히 CPU작업을 병렬화 했다 하더라도, 우리는 확실하게 PC의 여러 코어들에 작업을 분산시켜야 한다. 이것은 작업의 각각 다른 chunk들을 수행하기 위해 시간을 필요로 하는 것에 의해 복잡해진다. 또한, 우리는 종종 각각의 chunk들의 작업수행을 끝내기까지 요구하게 되는 작업이 얼마나 되는지 모른다.

For example, if Parallel.For were to assume that all iterations of the loop take the same amount of time, we could simply divide the range into as many contiguous ranges as we have cores, and assign each range to one core. Unfortunately, since the work per iteration may vary, it is possible that one core will end up with many expensive iterations, while other cores will have less work to do. In an extreme situation, one core may end up with nearly all work, and we are back to the sequential case.
: 예를 들어, 만약 Parallel.For로 구현한 Loop가 모두 같은 수행시간을 같는 다면, 우리는 우리가 가진 코어의 갯수에 따라 각 코어에 배당할 작업의 양을 간단하게 나눌 수 있다. 그러나 불행하게도, 각각 작업의 iteration이 다양하므로, 하나의 코어에 작업의 양이 큰 iteration들에 대한 작업이 끝난 다음에야 다음작업이 가능하면, 다른 코어들은 작업을 적게 할 것이다. 이러한 상황에서 하나의 코어가 모든 작업을 거의 끝낸다음 수행한다면, 우리는 sequential case로 다시 돌아가는 것이다.

Fortunately, our implementation of Parallel.For provides load balancing that should work well for most workloads. But, you are likely to encounter the load-balancing problem when writing your own concurrent code.
: 다행이도, Parallel.For의 구현은 가장 작업을 잘 수행할 수 있게 하는 load balancing을 제공한다. 그러나 스스로 코드를 작성할때 load-balancing문제를 겪을 수 있다.

Memory Allocations and Garbage Collection

Some programs spend a lot of time in memory allocations and garbage collections. For example, programs that manipulate strings tend to allocate a lot of memory, particularly if they are not designed carefully to prevent unnecessary allocations.
: 어떤 프로그램들은 메모리에 할당하고, 내리는 데에 많은 시간을 소비한다. 예를 들어, 프로그램이 String을 생성하여 메모리를 많이 사용하는 경우, 필요치 않은 메모리 할당을 주의해서 디자인 하지 않았다 할 수 있다.

Unfortunately, allocating memory is an operation that may require synchronization. After all, we need to ensure that memory regions allocated by different threads will not overlap.
: 불행하게, 메모리 할당은 synchronization을 요구하는 operation이다. 결과적으로, 우리는 overlap되지 않을 각각 다른 thread들에 의해 메모리를 할당하는 것을 필요로 한다.

Perhaps even more seriously, allocating a lot of memory typically means that we will also need to do a lot of garbage collection work to reclaim memory that has been freed. If the garbage collection dominates the running time of your program, the program will only scale as well as the garbage collection algorithm.
: 더욱 심각한 것은, 메모리 할당이 많다는 것은 결국 메모리에서 garbage collection 작업을 이용한 작업을 메모리에서 내리는 것을 많이 필요로 한다. 만약 garbage collection이 너의 프로그램의 실행시간에 상당부분 차지한다면, 프로그램은 garbage collection 알고리즘 만큼 수행시간이 늘어날 것이다.

It is possible to mitigate this issue by turning on the server GC. See Chris Lvon’s blog post Server, Workstation and Concurrent GC for more information about how server GC works and how to enable it.

False Cache-Line Sharing

In order to explain this particular performance problem of parallel programs, let’s quickly review a few details about how caches work on today’s mainstream computers. When a CPU reads a value from the main memory, it copies the value to cache, so that subsequent accesses to that value are much faster. In fact, rather than just bringing in that particular value into cache, the CPU will bring in also nearby memory locations. It turns out that if a program read a particular memory location, chances are that it is going to read nearby values too. So, values are moved between main memory and cache in chunks called cache lines, typically of size 64 or 128 bytes.
: Parallel 프로그램들의 일부 성능 문제를 설명하기 위해서, 오늘날 mainstream computer들에서 어떻게 작업이 cache되는지 보겠다. CPU가 메인 메모리에서 value값을 읽었을때, 그 값은 cache에 복사되며, 그래서 값에 접근하는데에 더 빨라지게 된다. 사실 단지 cache에서 일부 값을 가져오는 것 보다, CPU는 근처 memory location에서 가져오게 된다. 만약 프로그램이 일부 memeory location에서만 read작업을 한다면, 그 근처에 있는 값들이 read될 가능성이 높다. 그래서 value들은 main memory와 chunk들 안의 cache사이에서 움직이는데 이를 cache line이라고 부르며, 이것의 크기는 64 혹은 128 byte이다.

One problem that arises on machines with multiple cores is that if one core invalidates a particular memory location, the version of that memory location cached by another core gets invalidated. Then, the core with an invalid cached copy must go all the way to the main memory on the next read of that memory location. So, if two cores keep writing and reading a particular memory location, they may end up continuously invalidating each other’s caches, sometimes dramatically reducing the performance of the program.
: 멀티코어 PC에서 야기되는 문제는 만약 하나의 코어가 특정한 메모리 location을 무효화 한다면, 다른 코어가 무효화된 것을 할당받는 것에 의해 메모리 location의 정보가 캐쉬되어 진다. 그러면, invalid한 복사된 cache와 함께 코어는 반드시 main memory에서 memory location의 다음 정보를 읽어들여야 한다. 그래서 만약 두개의 코어가 특정 메모리 location에서 writing과 reading을 하고 있다면, 그들은 각각 서로 연속적이게 invalidating되는 것을 끝내여 하고, 때때로 이것은 프로그램의 성능을 감소시킨다.

The trickiest part of the issue is that the two cores don’t even have to be writing into the same memory location. The same problem occurs also if they are writing into two memory locations that are on the same cache line (hence the term “false cache-line sharing”).
: 이러한 issue의 애매한 부분은 두개의 코어들이 같은 메모리 위치에 writing작업을 할 수 없다는 것이다. 만약 그들이 두개의 메모리 위치에 같은 cache line을 사용하는 경우도 같은 문제가 발생되어진다.

Strangely, this problem turns up in practice fairly regularly. For example, a parallel program that computes the sum of integers in an array will typically have a separate intermediate result for each thread. The intermediate results are likely to be either elements in an array or fields in a class. And, in both cases, they would likely end up close in memory.
: 이상하게, 이 문제는 실제로 꽤 규칙적으로 발생한다. 예를 들어, 배열안에 integer값들을 합하는 연산을 하는 parallel program은 각 thread를 위해 결과를 분할하여 얻는다. 분할된 결과들은 배열이나 클래스의 변수들에 요소들과 같다. 그리고 그들은 마지막에 메모리에서 잠금된다.

There are various techniques to prevent false sharing, or at to at least make it unlikely: padding data structures with garbage data, allocating them in an order that makes false sharing less likely, or allocating them by different threads.
: 잘못된 공유를 예방하는데 다양한 방법들이 있다: garbage data와 함께 데이터 구조를 구성하거나, 잘못된 공유를 줄이기 위해 이들을 할당하거나 혹은 각 다른 thread들에 할당하는 방법들이 있다.

Locality Issues

Sometimes modifying a program to run in parallel negatively affects locality. For example, let’s say that we want to perform an operation on each element on an array. On a dual-core machine, we could create two tasks: one to perform the operation on the elements with even indices and one to handle odd indices.
: 때때로 Parallel로 프로그램을 실행시키기 위해 수정하는 것은 locality에 악영향을 주기도 한다. 예를들어, 우리가 배열의 각 요소에 대해 연산을 한다고 하자. 듀얼코어 PC에서, 우리는 두개의 task를 생성할 수 있다

But, as a negative consequence, the locality of reference degrades for each thread. The elements that a thread needs to access are interleaved with elements it does not care about. Each cache line will contain only half as many elements as it did previously, which may mean that twice as many memory accesses will go all the way to the main memory.
: 그러나 부정적인 결과 나왔을때, reference의 locality는 각각의 thread를 위해 degrade된다. Thread가 접근하기 위해 필요로 하는 element들은 각 요소들 사이에 끼워넣어지며 이 요소는 관여하지 않는다. 각 cache line은 이전의 많은 element들 만큼의 절반만을 더 포함하며, 이것은 메인메모리에 두배만큼의 많은 메모리 접근이 이루어지게 될 것임을 의미한다.(이 문단은 정확한 의미를 모르겠음;;;;;)

In this particular case, one solution is to split up the array into a left half and a right half, rather than odd and even elements. In more complicated cases, the problem and the solution may not be as obvious, so the effect of parallelization on locality of reference is one of the things to keep in mind when designing parallel algorithms.
: 일부 경우, 배열의 한쪽의 요소들만 쪼개는 것보다, 왼쪽절반과 오른쪽 절반을 쪼개는 것이 하나의 해결방법이다. 좀 더 복잡한 경우, 문제와 해법은 명백하지 않을 수 있으며, 그래서 reference의 locality에서의 병렬화의 영향력은 병렬 알고리즘을 설계했을때의 성향에 달려 있다.

Summary 

We discussed the most common reasons why a concurrent program may not achieve a parallel speedup that you would expect. If you keep these issues in mind, you should have an easier time designing and developing parallel programs