[Java] 자바 정적, 동적 쓰레드 할당 및 분석(소수 계산)

(a) environment

PC HANSUNG EH58

CPU Intel(R) Core(TM) i7-8700 CPU @ 3.2GHz to 4.3GHz. 6Core 12Thread

Memory size 32.0GB, 2400MHz

Disk PCIe SSD

OS Windows 10 Education(OS build : 21364.1000)

java java version "1.8.0_261"

Java(TM) SE Runtime Environment (build 1.8.0_261-b12)

Java HotSpot(TM) Client VM (build 25.261-b12, mixed mode, sharing)

openjdk-15.0.2

IDE

* This PC is equipped with a desktop CPU in the laptop, which causes severe temperature-induced throttling. To address this, we lower the CPU voltage by 0.15 V, but nevertheless show inconsistent results when throttling occurs.

 

 

(b) tables and graphs

 

(c) explanation/analysis on the results

static

In static load balancing, execution time has shown an overall decreasing trend. The section showing a marked performance improvement is when it is increased by a multiple of 2. However, intervals 6, 10, 12, and 14 show a slight increase. And there is little difference in 32. This can be explained for two main reasons. One is because of the method of dividing a set. The second is that the large number of threads theoretically leads to overhead due to context switching (but we can see that dynamic load balancing results do not have much effect below 512 threads).

 

Theoretically, the PC is expected to have the highest efficiency at 12 threads. But in the actual table, at 6, 10, 12, 14 some threads end too quickly. It appears to be due to inadequate dispersion. In that code, the set was constructed as follows.

 

If there are t threads

1. The n-th thread handles the numbers 2n - 1. {n| 1 <= n <= c}

2. The n-th thread processes the numbers 2n - 1 + t by adding t to the number previously processed.

3. Exit if the number exceeds NUM_END.

 

The reason for this composition is that I wanted to reduce unnecessary operations related to multiples of 2. However, this method does not prevent other small prime number of multiples, e.g., multiples of 3, multiples of 5. Therefore, at 6 (multiple of 3), 10 (multiple of 5), 12 (multiple of 3), and 14 (multiple of 7), some threads performed unnecessary operations. This causes unnecessary overhead, which reduces performance. Generalizing this, the problem arises when 2t have a common divisor among odd numbers from 1 to 2t–1. And this explains why threads work well when they are multiples of 2.

 

Based on the above results, to get a number of prime number through static load balancing, it is expected to perform well if the set is well distributed according to the number of threads the PC has. On an average PC, the number of cores is not large, so it will be efficient to get them by hand, but if you use many cores like grid computing, it will be more efficient to get them using a different approach like using Eratosthenes sieve.

 

dynamic

Dynamic load balancing does not cause problems that static load balancing showed, because of effectively distributed set. However, to see if the difference between 16 and 32 is really due to context switching, I tested it with NUM_END is 1000000 and NUM_THREAD is from 1 to 65536.

 

Is it really true that threads that match CPU threads perform best?

 

To begin with, it is not true in this case. The graph is as below. Here I also include thread generation time. I expected if the generating lots of threads affects execution time. It is also not true. Even if the number of threads is raised to 8192, there is no significant change on execution time. On the contrary, it showed a steady decline to 512 threads compared to 12 threads expected in theory. What is noteworthy is the inaccuracy of results. When there were more than 1,024 threads, the results were inaccurate.

 

The overhead caused by context switching in many threads seems to come from over 8192 threads. The phrase "many threads consume unnecessary resources by causing a lot of context switching," commonly known on the Internet, does not seem to fit at least in the corresponding code and in this environment. This result tells that we need to study more in-depth how JVM manages thread pools.

 

Limits

There are a number of variables in the environment that might affect the test including CPU throttling due to temperature, performance by size of RAM, actual number of cores used, and other programs running in the background. But "Is it really true that threads that match CPU threads perform best?" The results from 12 to 512 on the graph are able to provide evidence that the above question could not be answered as a definite yes. The results of the execution of the graph below were stored in thread65536.txt.

 

(d).a your entire JAVA source code

 

pc_static

 

/*쓰레드별로 판단할 소수를 분할해주는 방법
 * 정적 로드밸런싱을 통한 소수 판별
 * 쓰레드 갯수를 NUM_THREAD로 미리 정해준다.
 *
 * 단순하게 1~NUM_END까지를 NUM_THREAD로 나눠주면 쓰레드별로 부하가 크게 차이난다.
 * ex.1~800까지일 때 [1,100],...,[700,800]에서 [700,800]이 부하가 훨씬 크다.
 * 그렇기에 1~NUM_END을 적절하게 나누어 쓰레드마다 받을 부하를 비슷하게 해준다.
 *
 * 가장 간단하게 하는 방법? 쓰레드별로 쓰레드 각각의 번호부터 NUM_THREAD 만큼씩 더한 값을 판별한다.
 * ex. NUM_THREAD = 2? [1, 3, 5, 7, ..., 1+2n, ...], [2, 4, 6, 8, ..., 2+2n, ...]
 * 장점? 분할이 효과적으로 된다.
 * 단점? 이또한 제대로 분할이 되지 않는다. 짝수를 담당하는 쓰레드는 훨씬 빨리 끝난다.
 *
 * 단점해결?
 * 짝수는 계산하지 않는다. 다만 짝수 2를 카운트하기 위해 미리 1 추가
 * [1, 5, 9, ..., n + 2*NUM_THREAD], [3, 7, 11, ..., n + 2*NUM_THREAD]
 * 로 해준다.
 * serial도 동일하게 해주기 위해 짝수만 계산하자.
 * */

public class pc_static {
    // 20만까지 테스트하기 위함
    private static final int NUM_END = 200000;
    private static final int NUM_THREAD = 2;

    // 메인함수
    public static void main(String[] args) throws InterruptedException {
        // 소수의 수를 저장하기 위한 counter. 짝수 2를 카운트하기 위해 미리 1 추가
        thread_static.counter = 1;
        // for 문에서 소수를 테스트하기 위한 변수
        int i;

        // 쓰레드 생성 및 변수 할당
        thread_static[] thread = new thread_static[NUM_THREAD];
        // 쓰레드에 시작값 할당
        for (int t = 0; t < NUM_THREAD; t++) {
            // 배열은 0부터 시작이라 0에는 1을, 1에는 3을 할당하기 위해 1 추가.
            thread[t] = new thread_static(1 + t * 2);
        }

        //시작 시간을 측정하기 위한 변수
        long startTime = System.currentTimeMillis();
        // 소수인지 테스트
        // 쓰레드 시작
        for (int t = 0; t < NUM_THREAD; t++) {
            thread[t].start();
        }
        // 시간 측정을 위해 join 을 이용해 쓰레드가 끝날 때까지 대기
        for (int t = 0; t < NUM_THREAD; t++) {
            thread[t].join();
        }

        // 끝나는 시간을 측정하기 위한 변수
        long endTime = System.currentTimeMillis();
        // 실제 실행 시간이 얼마인지를 측정하기 위한 변수
        long timeDiff = endTime - startTime;

        // (1) execution time of each thread
        // 쓰레드별 실행 시간 출력문
        for (int t = 0; t < NUM_THREAD; t++) {
            System.out.println("Thread-" + t + "'s Execution Time : " + thread[t].timeDiff + "ms");
        }

        // (2) execution time when using all threads
        // 전체 실행 시간 출력문
        System.out.println("Execution Time : " + timeDiff + "ms");

        // 1부터 NUM_END-1까지의 소수의 갯수 출력문
        System.out.println("1..." + (NUM_END - 1) + " prime# counter=" + thread_static.counter + "\n");

    }

    // 소수 판별 함수. 판별하기 위한 숫자를 x로 받는다.
    private static boolean isPrime(int x) {
        // 임시 변수 i 설정
        int i;
        // 받은 숫자가 1이라면 false 반환
        if (x <= 1) return false;
        // i를 2부터 x-1까지 실행한다.
        for (i = 2; i < x; i++) {
            // 만약 x가 i로 나누어지고(% 연산 시 0 출력) i가 x가 아니라면 소수가 아니니 false 반환
            // 사실 여기는 코드를 단순화 가능
            if (((x % i) == 0) && (i != x)) return false;
        }
        return true;
    }

    static class thread_static extends Thread {
        // 쓰레드에서 처음 판단할 숫자를 변수 x로 주었다.
        int x;
        // 소수 숫자를 세기 위해 counter 변수를 클래스 내에 선언해줬다.
        static int counter;
        // 쓰레드 끝난 후 더하기 위해 임시 변수 선언
        int temp = 0;
        // 쓰레드 시작 시간
        long startTime;
        // 쓰레드 종료 시간
        long endTime;
        // 쓰레드 실행 시간
        long timeDiff;

        // constructor, 생성자로 변수 전달
        public thread_static(int x) {
            this.x = x;
        }

        public void run() {
            // 쓰레드 시작 시간
            startTime = System.currentTimeMillis();

            // 소수 판별용 변수 i
            int i;
            // x :: 처음 판단할 숫자
            // i<NUM_END :: i부터 NUM_END-1 까지
            // i = i+NUM_THREAD :: i부터 판단할 숫자는 NUM_THREAD 씩 더한다.
            for (i = x; i < NUM_END; i = i + NUM_THREAD * 2) {
                // 소수이면 temp 에 1을 더한다.
                if (isPrime(i)) temp++;
            }

            // 클래스 내 counter 변수에 소수를 더한다.
            counter += temp;
            // 쓰레드 종료 시간
            endTime = System.currentTimeMillis();
            // 쓰레드 실행 시간
            timeDiff = endTime - startTime;
        }
    }
}

pc_dynamic

 

/*쓰레드별로 판단할 소수를 분할해주는 방법
 * 동적 로드밸런싱을 통한 소수 판별
 *
 * 1~NUM_THREAD 까지 isPrime 변수를 1부터 2씩 추가해간다.
 * 이때 isPrime 변수를 synchronized 를 사용하여 충돌하지 않도록 업데이트 해준다.
 *
 * 쓰레드 갯수를 NUM_THREAD 로 미리 정해준다.
 *
 *
 * */

public class pc_dynamic {
    // 20만까지 테스트하기 위함
    private static final int NUM_END = 1000000;
    private static final int NUM_THREAD = 1;

    // 메인함수
    public static void main(String[] args) throws InterruptedException {
        // 소수의 수를 저장하기 위한 counter. 짝수 2를 카운트하기 위해 미리 1 추가
        thread_dynamic.counter = 1;
        // for 문에서 소수를 테스트하기 위한 변수
        int i;

        // 쓰레드 생성에 따른 시간 차이를 알기 위해 입력한 시간
        //long startTimeReal = System.currentTimeMillis();


        // 쓰레드 생성
        thread_dynamic[] thread = new thread_dynamic[NUM_THREAD];
        // 쓰레드에 시작값 할당
        // isPrime 는  처음 할당된 값들 이후부터 계산할 것이다.
        for (int t = 0; t < NUM_THREAD; t++) {
            // 배열은 0부터 시작이라 0에는 1을, 1에는 3을 할당하기 위해 1 추가.
            thread[t] = new thread_dynamic(1 + t * 2);
        }
        // 판단을 시작할 변수를 할당해줬다.
        thread_dynamic.isPrime = NUM_THREAD * 2 - 1;

        //시작 시간을 측정하기 위한 변수
        long startTime = System.currentTimeMillis();
        // 소수인지 테스트
        // 쓰레드 시작
        for (int t = 0; t < NUM_THREAD; t++) {
            thread[t].start();
        }
        // 시간 측정을 위해 join 을 이용해 쓰레드가 끝날 때까지 대기
        for (int t = 0; t < NUM_THREAD; t++) {
            thread[t].join();
        }

        // 끝나는 시간을 측정하기 위한 변수
        long endTime = System.currentTimeMillis();
        // 실제 실행 시간이 얼마인지를 측정하기 위한 변수
        long timeDiff = endTime - startTime;

        // 쓰레드 생성에 따른 시간 차이를 알기 위해 입력한 시간
        //long timeDiffReal = endTime - startTimeReal;

        // (1) execution time of each thread
        // 쓰레드별 실행 시간 출력문
        for (int t = 0; t < NUM_THREAD; t++) {
            System.out.println("Thread-" + t + "'s Execution Time : " + thread[t].timeDiff + "ms");
        }

        for (int t = 0; t < NUM_THREAD; t++) {
            System.out.println("Thread-" + t + "'s temp : " + thread[t].temp);
        }

        // (2) execution time when using all threads
        // 전체 실행 시간 출력문
        System.out.println("Execution Time : " + timeDiff + "ms");
        // 생성 포함한 전체 실행 시간 출력문
        //System.out.println("Real Execution Time : " + timeDiffReal + "ms");


        // 1부터 NUM_END-1까지의 소수의 갯수 출력문
        System.out.println("1..." + (NUM_END - 1) + " prime# counter=" + thread_dynamic.counter + "\n");

    }

    // 소수 판별 함수. 판별하기 위한 숫자를 x로 받는다.
    private static boolean isPrime(int x) {
        // 임시 변수 i 설정
        int i;
        // 받은 숫자가 1이라면 false 반환
        if (x <= 1) return false;
        // i를 2부터 x-1까지 실행한다.
        for (i = 2; i < x; i++) {
            // 만약 x가 i로 나누어지고(% 연산 시 0 출력) i가 x가 아니라면 소수가 아니니 false 반환
            // 사실 여기는 코드를 단순화 가능
            if (((x % i) == 0) && (i != x)) return false;
        }
        return true;
    }

    static class thread_dynamic extends Thread {
        // 쓰레드에서 처음 판단할 숫자를 변수 x로 주었다.
        //  isPrime 에서 x를 할당 받아올 것이다.
        int x;
        // 소수 숫자를 세기 위해 counter 변수를 클래스 내에 선언해줬다.
        static int counter;
        // 소수인지 확인할 변수를 변수를 클래스 내에 선언해줬다.
        static int isPrime;
        // 쓰레드 끝난 후 더하기 위해 임시 변수 선언
        int temp = 0;
        // 쓰레드 시작 시간
        long startTime;
        // 쓰레드 종료 시간
        long endTime;
        // 쓰레드 실행 시간
        long timeDiff;

        public thread_dynamic(int x) {
            this.x = x;
        }

        public void run() {
            // 쓰레드 시작 시간
            startTime = System.currentTimeMillis();

            // isPrime 는 판단할 변수를 의미하는데 이것이 NUM_END 를 넘어가면 종료하도록 했다.
            while (isPrime < NUM_END) {
                {
                    if (isPrime(this.x)) temp++;
                    //순서 중요하다. 할당된 것을 계산하고 업데이트해줘야 한다.
                    this.x = update();
                }
            }

            // 클래스 내 counter 변수에 소수를 더한다.
            counter += temp;

            // 쓰레드 종료 시간
            endTime = System.currentTimeMillis();
            // 쓰레드 실행 시간
            timeDiff = endTime - startTime;
        }

        //여기를 synchronized 로 해줬다. x 를 isPrime 에서 가져오고 isPrime 는 2 더해준다.
        static synchronized int update() {
            isPrime = isPrime + 2;
            return isPrime;
        }
    }
}

 

(d).b screen capture image of program execution and output.

static

dynamic