assignment2 - Katyusha's blog

环境

OS wsl2 6.6.87.2-microsoft-standard-WSL2 Ubuntu 24.04.3 LTS

CPU: Intel Core i7 13620H 8 cores, 10 logic processors, AVX2

GPU GeForce RTX 4060 Laptop

assignment2#

这一部分要求你补全一个类似于ISPC的任务系统，其余部分已经完成，你需要完成负载分配部分

你需要完成无依赖和有依赖的任务系统，并且要用每次创建线程，使用线程池且线程自旋，使用线程池且线程休眠三种方式实现

无依赖的任务系统#

每次创建线程#

这是trivial的，每次创建线程执行任务即可，为了平均负载，每当有空闲进程时就取出下一个任务来给该线程执行

注意当前执行到了哪一个进程这个变量会被多个线程使用，需要声明为原子变量

1
class TaskSystemParallelSpawn: public ITaskSystem {
2
    public:
3
        TaskSystemParallelSpawn(int num_threads);
4
        ~TaskSystemParallelSpawn() override;
5
        const char* name();
6
        void run(IRunnable* runnable, int num_total_tasks);
7
        TaskID runAsyncWithDeps(IRunnable* runnable, int num_total_tasks,
8
                                const std::vector<TaskID>& deps);
9
        void sync();
10
    private:
11
        int Num_Threads;
12
        std::atomic <int> task_ptr;
13
        std::thread *thread_ptr;
14
};
15

16
//tasksys.cpp
17
const char* TaskSystemParallelSpawn::name() {
18
    return "Parallel + Always Spawn";
19
}
20

21
TaskSystemParallelSpawn::TaskSystemParallelSpawn(int num_threads)
22
    : ITaskSystem(num_threads),
23
      Num_Threads(num_threads),
24
      thread_ptr(new std::thread[num_threads]),
25
      task_ptr(0) {
26

27
    //
28
    // TODO: CS149 student implementations may decide to perform setup
29
    // operations (such as thread pool construction) here.
30
    // Implementations are free to add new class member variables
31
    // (requiring changes to tasksys.h).
32
    //
33
}
34

35
TaskSystemParallelSpawn::~TaskSystemParallelSpawn() {
36
    delete[] thread_ptr;
37
}
38

39
void TaskSystemParallelSpawn::run(IRunnable* runnable, int num_total_tasks){
40

41
    //
42
    // TODO: CS149 students will modify the implementation of this
43
    // method in Part A.  The implementation provided below runs all
44
    // tasks sequentially on the calling thread.
45
    //
46
    task_ptr = 0;
47
    auto work = [&]() {
48
        while(1) {
49
            int task_id = task_ptr.fetch_add(1);
50
            if (task_id >= num_total_tasks) break;
51
            runnable->runTask(task_id, num_total_tasks);
52
        }
53
    };
54

55
    for (int i = 0; i < Num_Threads; i++) {
56
        thread_ptr[i] = std::thread(work);
57
    }
58
    for (int i = 0; i < Num_Threads; i++) {
59
        thread_ptr[i].join();
60
    }
61
}
62

63
TaskID TaskSystemParallelSpawn::runAsyncWithDeps(IRunnable* runnable, int num_total_tasks,
64
                                                 const std::vector<TaskID>& deps) {
65
    // You do not need to implement this method.
66
    return 0;
67
}
68

69
void TaskSystemParallelSpawn::sync() {
70
    // You do not need to implement this method.
71
    return;
72
}

自旋线程池#

每次都创建线程会产生额外的开销，为了减少开销，可以在任务系统被创建的时候就创建线程，在需要的时候执行任务，否则自旋，当任务系统调用析构函数的时候，结束所有线程

1
class TaskSystemParallelThreadPoolSpinning: public ITaskSystem {
2
    public:
3
        TaskSystemParallelThreadPoolSpinning(int num_threads);
4
        ~TaskSystemParallelThreadPoolSpinning();
5
        const char* name();
6
        void run(IRunnable* runnable, int num_total_tasks);
7
        TaskID runAsyncWithDeps(IRunnable* runnable, int num_total_tasks,
8
                                const std::vector<TaskID>& deps);
9
        void sync();
10
    private:
11
        int Num_Threads;
12
        std::thread *thread_ptr;
13
        IRunnable *task;
14
        int task_num;
15
        std::atomic <bool> end;
16
        std::atomic<int> task_ptr, task_done;
17
        std::mutex mtx;
18
};
19

20
//tasksys.cpp
21
const char* TaskSystemParallelThreadPoolSpinning::name() {
22
    return "Parallel + Thread Pool + Spin";
23
}
24

25
TaskSystemParallelThreadPoolSpinning::TaskSystemParallelThreadPoolSpinning(int num_threads)
26
    : ITaskSystem(num_threads),
27
      Num_Threads(num_threads),
28
      thread_ptr(new std::thread[num_threads]),
29
      task(nullptr),
30
      task_num(0),
31
      task_ptr(0),
32
      end(false) {
33

34
    //
35
    // TODO: CS149 student implementations may decide to perform setup
36
    // operations (such as thread pool construction) here.
37
    // Implementations are free to add new class member variables
38
    // (requiring changes to tasksys.h).
39
    //
40

41
    auto work = [&]() {
42
        while (1) {
43
            if (end) break;
44
            int task_id = -1; {
45
                std::unique_lock <std::mutex> lock(mtx);
46
                if (task_ptr < task_num) {
47
                    task_id = task_ptr;
48
                    task_ptr++;
49
                }
50
            }
51

52
            if (task_id != -1) {
53
                task->runTask(task_id, task_num);
54
                task_done.fetch_add(1);
55
            }
56
        }
57
    };
58

59
    for (int i = 0; i < num_threads; i++) {
60
        thread_ptr[i] = std::thread(work);
61
    }
62
}
63

64
TaskSystemParallelThreadPoolSpinning::~TaskSystemParallelThreadPoolSpinning() {
65
    end = true;
66
    for (int i = 0; i < Num_Threads; i++) {
67
        thread_ptr[i].join();
68
    }
69
    delete[] thread_ptr;
70
}
71

72
void TaskSystemParallelThreadPoolSpinning::run(IRunnable* runnable, int num_total_tasks) {
73

74

75
    //
76
    // TODO: CS149 students will modify the implementation of this
77
    // method in Part A.  The implementation provided below runs all
78
    // tasks sequentially on the calling thread.
79
    //
80
    mtx.lock();
81
    task = runnable;
82
    task_num = num_total_tasks;
83
    task_ptr = 0;
84
    task_done = 0;
85
    mtx.unlock();
86
    while (task_done < task_num) {}
87
}
88

89
TaskID TaskSystemParallelThreadPoolSpinning::runAsyncWithDeps(IRunnable* runnable, int num_total_tasks,
90
                                                              const std::vector<TaskID>& deps) {
91
    // You do not need to implement this method.
92
    return 0;
93
}
94

95
void TaskSystemParallelThreadPoolSpinning::sync() {
96
    // You do not need to implement this method.
97
    return;
98
}

休眠线程池#

当一个线程在没有任务自旋的时候，仍然会占用CPU，考虑在没有剩余任务的时候让线程自旋

C++提供了条件变量condition_variable来进行控制

对于一个条件变量，可以通过其成员函数wait(std::unique_lock, pred) 使得拥有指定的互斥锁的线程休眠，直到接到通知并且pred为true(如果不设置pred，可能出现丢失唤醒和虚假唤醒)；通过成员函数notify_all/one 来通知该条件变量的所有/随机一个线程

1
class TaskSystemParallelThreadPoolSleeping: public ITaskSystem {
2
    public:
3
        TaskSystemParallelThreadPoolSleeping(int num_threads);
4
        ~TaskSystemParallelThreadPoolSleeping();
5
        const char* name();
6
        void run(IRunnable* runnable, int num_total_tasks);
7
        TaskID runAsyncWithDeps(IRunnable* runnable, int num_total_tasks,
8
                                const std::vector<TaskID>& deps);
9
        void sync();
10
    private:
11
        int Num_Threads;
12
        std::thread *thread_ptr;
13
        IRunnable *task;
14
        int task_num;
15
        std::atomic <bool> end;
16
        std::atomic<int> task_ptr, task_done;
17
        std::mutex mtx;
18
        std::condition_variable cond;
19
};
20

21
//tasksys.cpp
22
const char* TaskSystemParallelThreadPoolSleeping::name() {
23
    return "Parallel + Thread Pool + Sleep";
24
}
25

26
TaskSystemParallelThreadPoolSleeping::TaskSystemParallelThreadPoolSleeping(int num_threads)
27
    : ITaskSystem(num_threads),
28
      Num_Threads(num_threads),
29
      thread_ptr(new std::thread[num_threads]),
30
      task(nullptr),
31
      end(false),
32
      task_num(0),
33
      task_done(0),
34
      task_ptr(0) {
35
    //
36
    // TODO: CS149 student implementations may decide to perform setup
37
    // operations (such as thread pool construction) here.
38
    // Implementations are free to add new class member variables
39
    // (requiring changes to tasksys.h).
40
    //
41

42
    auto work = [&]() {
43
        while (1) {
44
            int task_id = -1; {
45
                std::unique_lock <std::mutex> lock(mtx);
46
                cond.wait(lock, [&]() {
47
                    return (task_ptr < task_num) || end;
48
                });
49
                if (end) break;
50
                task_id = task_ptr;
51
                task_ptr++;
52
            }
53

54
            if (task_id != -1) {
55
                task->runTask(task_id, task_num);
56
                task_done.fetch_add(1);
57
            }
58
        }
59
    };
60
    for (int i = 0; i < Num_Threads; i++) {
61
        thread_ptr[i] = std::thread(work);
62
    }
63
}
64

65
TaskSystemParallelThreadPoolSleeping::~TaskSystemParallelThreadPoolSleeping() {
66
    //
67
    // TODO: CS149 student implementations may decide to perform cleanup
68
    // operations (such as thread pool shutdown construction) here.
69
    // Implementations are free to add new class member variables
70
    // (requiring changes to tasksys.h).
71
    //
72
    end = 1;
73
    cond.notify_all();
74
    for (int i = 0; i < Num_Threads; i++) {
75
        thread_ptr[i].join();
76
    }
77
}
78

79
void TaskSystemParallelThreadPoolSleeping::run(IRunnable* runnable, int num_total_tasks) {
80

81

82
    //
83
    // TODO: CS149 students will modify the implementation of this
84
    // method in Parts A and B.  The implementation provided below runs all
85
    // tasks sequentially on the calling thread.
86
    //
87
    mtx.lock();
88
    task = runnable;
89
    task_num = num_total_tasks;
90
    task_done = 0;
91
    task_ptr = 0;
92
    mtx.unlock();
93
    cond.notify_all();
94
    while (task_done < task_num) {}
95

96
}
97

98
TaskID TaskSystemParallelThreadPoolSleeping::runAsyncWithDeps(IRunnable* runnable, int num_total_tasks,
99
                                                    const std::vector<TaskID>& deps) {
100

101

102
    //
103
    // TODO: CS149 students will implement this method in Part B.
104
    //
105

106
    return 0;
107
}
108

109
void TaskSystemParallelThreadPoolSleeping::sync() {
110

111
    //
112
    // TODO: CS149 students will modify the implementation of this method in Part B.
113
    //
114

115
    return;
116
}

测试结果如下

1
katyusha@Katyusha-PC:~/lesson/CS149/asst2/part_a$ python3 ../tests/run_test_harness.py
2
runtasks_ref
3
Linux x86_64
4
================================================================================
5
Running task system grading harness... (11 total tests)
6
  - Detected CPU with 16 execution contexts
7
  - Task system configured to use at most 16 threads
8
================================================================================
9
================================================================================
10
Executing test: super_super_light...
11
Reference binary: ./runtasks_ref_linux
12
Results for: super_super_light
13
                                        STUDENT   REFERENCE   PERF?
14
[Serial]                                3.047     3.205       0.95  (OK)
15
[Parallel + Always Spawn]               187.19    185.967     1.01  (OK)
16
[Parallel + Thread Pool + Spin]         17.331    24.842      0.70  (OK)
17
[Parallel + Thread Pool + Sleep]        49.395    50.039      0.99  (OK)
18
================================================================================
19
Executing test: super_light...
20
Reference binary: ./runtasks_ref_linux
21
Results for: super_light
22
                                        STUDENT   REFERENCE   PERF?
23
[Serial]                                40.591    39.736      1.02  (OK)
24
[Parallel + Always Spawn]               192.036   192.494     1.00  (OK)
25
[Parallel + Thread Pool + Spin]         16.801    28.911      0.58  (OK)
26
[Parallel + Thread Pool + Sleep]        50.339    49.974      1.01  (OK)
27
================================================================================
28
Executing test: ping_pong_equal...
29
Reference binary: ./runtasks_ref_linux
30
Results for: ping_pong_equal
31
                                        STUDENT   REFERENCE   PERF?
32
[Serial]                                647.781   650.243     1.00  (OK)
33
[Parallel + Always Spawn]               226.69    232.931     0.97  (OK)
34
[Parallel + Thread Pool + Spin]         127.354   151.776     0.84  (OK)
35
[Parallel + Thread Pool + Sleep]        141.546   151.333     0.94  (OK)
36
================================================================================
37
Executing test: ping_pong_unequal...
38
Reference binary: ./runtasks_ref_linux
39
Results for: ping_pong_unequal
40
                                        STUDENT   REFERENCE   PERF?
41
[Serial]                                1190.3    1201.024    0.99  (OK)
42
[Parallel + Always Spawn]               296.642   301.453     0.98  (OK)
43
[Parallel + Thread Pool + Spin]         191.766   201.452     0.95  (OK)
44
[Parallel + Thread Pool + Sleep]        205.871   201.991     1.02  (OK)
45
================================================================================
46
Executing test: recursive_fibonacci...
47
Reference binary: ./runtasks_ref_linux
48
Results for: recursive_fibonacci
49
                                        STUDENT   REFERENCE   PERF?
50
[Serial]                                563.32    1044.844    0.54  (OK)
51
[Parallel + Always Spawn]               96.153    147.336     0.65  (OK)
52
[Parallel + Thread Pool + Spin]         95.011    161.128     0.59  (OK)
53
[Parallel + Thread Pool + Sleep]        95.246    136.351     0.70  (OK)
54
================================================================================
55
Executing test: math_operations_in_tight_for_loop...
56
Reference binary: ./runtasks_ref_linux
57
Results for: math_operations_in_tight_for_loop
58
                                        STUDENT   REFERENCE   PERF?
59
[Serial]                                321.704   364.809     0.88  (OK)
60
[Parallel + Always Spawn]               902.166   959.155     0.94  (OK)
61
[Parallel + Thread Pool + Spin]         109.294   148.513     0.74  (OK)
62
[Parallel + Thread Pool + Sleep]        233.708   260.56      0.90  (OK)
63
================================================================================
64
Executing test: math_operations_in_tight_for_loop_fewer_tasks...
65
Reference binary: ./runtasks_ref_linux
66
Results for: math_operations_in_tight_for_loop_fewer_tasks
67
                                        STUDENT   REFERENCE   PERF?
68
[Serial]                                355.836   368.551     0.97  (OK)
69
[Parallel + Always Spawn]               956.475   954.91      1.00  (OK)
70
[Parallel + Thread Pool + Spin]         152.932   179.352     0.85  (OK)
71
[Parallel + Thread Pool + Sleep]        258.914   261.421     0.99  (OK)
72
================================================================================
73
Executing test: math_operations_in_tight_for_loop_fan_in...
74
Reference binary: ./runtasks_ref_linux
75
Results for: math_operations_in_tight_for_loop_fan_in
76
                                        STUDENT   REFERENCE   PERF?
77
[Serial]                                184.691   187.97      0.98  (OK)
78
[Parallel + Always Spawn]               129.168   125.984     1.03  (OK)
79
[Parallel + Thread Pool + Spin]         39.776    45.638      0.87  (OK)
80
[Parallel + Thread Pool + Sleep]        51.235    53.255      0.96  (OK)
81
================================================================================
82
Executing test: math_operations_in_tight_for_loop_reduction_tree...
83
Reference binary: ./runtasks_ref_linux
84
Results for: math_operations_in_tight_for_loop_reduction_tree
85
                                        STUDENT   REFERENCE   PERF?
86
[Serial]                                185.884   190.249     0.98  (OK)
87
[Parallel + Always Spawn]               57.856    58.765      0.98  (OK)
88
[Parallel + Thread Pool + Spin]         38.416    38.12       1.01  (OK)
89
[Parallel + Thread Pool + Sleep]        41.4      38.552      1.07  (OK)
90
================================================================================
91
Executing test: spin_between_run_calls...
92
Reference binary: ./runtasks_ref_linux
93
Results for: spin_between_run_calls
94
                                        STUDENT   REFERENCE   PERF?
95
[Serial]                                219.686   373.554     0.59  (OK)
96
[Parallel + Always Spawn]               112.957   191.493     0.59  (OK)
97
[Parallel + Thread Pool + Spin]         192.487   238.134     0.81  (OK)
98
[Parallel + Thread Pool + Sleep]        122.142   191.913     0.64  (OK)
99
================================================================================
100
Executing test: mandelbrot_chunked...
101
Reference binary: ./runtasks_ref_linux
102
Results for: mandelbrot_chunked
103
                                        STUDENT   REFERENCE   PERF?
104
[Serial]                                273.413   274.303     1.00  (OK)
105
[Parallel + Always Spawn]               30.291    28.085      1.08  (OK)
106
[Parallel + Thread Pool + Spin]         25.06     26.769      0.94  (OK)
107
[Parallel + Thread Pool + Sleep]        26.543    25.636      1.04  (OK)
108
================================================================================
109
Overall performance results
110
[Serial]                                : All passed Perf
111
[Parallel + Always Spawn]               : All passed Perf
112
[Parallel + Thread Pool + Spin]         : All passed Perf
113
[Parallel + Thread Pool + Sleep]        : All passed Perf

有依赖的任务系统#

要求你在休眠线程池功能基础上，实现runAsyncWithDeps函数，该函数相较于run还传入了一个std::vector<TaskID>参数，用来表示前置需要完成的任务集合，返回值为该任务的TaskID。该任务与run中的任务异步执行，直到调用sync()函数，阻塞主线程直到所有的依赖任务都已经完成

可以将run看做一个特殊的无依赖的任务，在对其调用runAsyncWithDeps后立即sync()同步

我们使用了队列来维护可执行的任务(即所有前置任务都已经完成的任务)，每次一个线程都尝试在队列中取出任务进行执行。

为了维护任务间的依赖关系，我们对每个任务都维护了一个suf集合，用来表示依赖于该任务的后继。当一个任务子任务全部完成时，就更新其所有后继的状态，若一个后继的前置任务全部完成，就将该后继加入队列；当申请一个新的任务时，对于其未完成的前置任务，尝试更新其suf集合

在实现上存在诸多细节，比如使用vector的话，原本有效的迭代器可能因为其他线程操作扩容而导致失效造成悬空引用，可以使用deque，unordered_map数据结构进行替代，或者采用下标索引；在效率方面尽量少使用互斥锁，多使用原子变量并且在必须使用互斥锁的时候只进行简单的标记，记录等操作

1
class TaskSystemParallelThreadPoolSleeping: public ITaskSystem {
2
    public:
3
        TaskSystemParallelThreadPoolSleeping(int num_threads);
4
        ~TaskSystemParallelThreadPoolSleeping();
5
        const char* name();
6
        void run(IRunnable* runnable, int num_total_tasks);
7
        TaskID runAsyncWithDeps(IRunnable* runnable, int num_total_tasks,
8
                                const std::vector<TaskID>& deps);
9
        void sync();
10
    private:
11
        std::thread *thread_ptr;
12
        IRunnable *task;
13
        int Num_threads;
14
        int task_done = 0;
15
        std::queue<TaskID> task_que;
16
        struct Task {
17
            std::vector <int> suf;
18
            IRunnable *task;
19
            std::atomic<int> task_ptr{0}, task_done{0}, pre_done{0};
20
            int task_num, pre_cnt;
21
            Task() {}
22
            Task(IRunnable *T, int Task_num, int Pre_cnt)
23
                : task(T),
24
                  task_num(Task_num),
25
                  pre_cnt(Pre_cnt) {
26

27
            }
28
        };
29
        std::vector <Task*> task_vec;
30
        std::mutex mtx;
31
        std::condition_variable work_cv, sync_cv;
32
        bool end = false;
33
};
34

35
//tasksys.cpp
36

37
/*
38
 * ================================================================
39
 * Parallel Thread Pool Sleeping Task System Implementation
40
 * ================================================================
41
 */
42

43
const char* TaskSystemParallelThreadPoolSleeping::name() {
44
    return "Parallel + Thread Pool + Sleep";
45
}
46

47
TaskSystemParallelThreadPoolSleeping::TaskSystemParallelThreadPoolSleeping(int num_threads)
48
    : ITaskSystem(num_threads),
49
      Num_threads(num_threads),
50
      thread_ptr(new std::thread[num_threads]),
51
      end(false),
52
      task_done(0) {
53
    //
54
    // TODO: CS149 student implementations may decide to perform setup
55
    // operations (such as thread pool construction) here.
56
    // Implementations are free to add new class member variables
57
    // (requiring changes to tasksys.h).
58
    //
59
    auto work = [&]() {
60
        while (1) {
61
            int task_id = -1, subtask_id = -1;
62
            Task *ptr = nullptr; {
63
                std::unique_lock <std::mutex> lock(mtx);
64
                work_cv.wait(lock, [&]() {
65
                    return (!task_que.empty()) || end;
66
                });
67
                if (end && task_que.empty()) break;
68
                task_id = task_que.front();
69
                ptr = task_vec[task_id];
70
                if (ptr->task_ptr >= ptr->task_num) {
71
                    task_que.pop();
72
                    continue;
73
                }
74
            }
75

76
            if (ptr != nullptr) {
77
                while (1) {
78
                    subtask_id = ptr->task_ptr.fetch_add(1);
79
                    if (subtask_id >= ptr->task_num) break;
80
                    ptr->task->runTask(subtask_id, ptr->task_num);
81
                    int done = ptr->task_done.fetch_add(1) + 1;
82
                    if (done == ptr->task_num){
83
                        std::unique_lock <std::mutex> lock(mtx);
84
                        ++task_done;
85
                        for (const auto &idx : ptr->suf) {
86
                            Task *_ptr = task_vec[idx];
87
                            if (++_ptr->pre_done == _ptr->pre_cnt) {
88
                                task_que.push(idx);
89
                                work_cv.notify_all();
90
                            }
91
                        }
92
                        sync_cv.notify_all();
93
                    }
94
                }
95
            }
96
        }
97
    };
98
    for (int i = 0; i < Num_threads; i++) {
99
        thread_ptr[i] = std::thread(work);
100
    }
101
}
102

103
TaskSystemParallelThreadPoolSleeping::~TaskSystemParallelThreadPoolSleeping() {
104
    //
105
    // TODO: CS149 student implementations may decide to perform cleanup
106
    // operations (such as thread pool shutdown construction) here.
107
    // Implementations are free to add new class member variables
108
    // (requiring changes to tasksys.h).
109
    //
110
    std::unique_lock <std::mutex> lock(mtx);
111
    end = 1;
112
    lock.unlock();
113
    work_cv.notify_all();
114
    for (int i = 0; i < Num_threads; i++) {
115
        thread_ptr[i].join();
116
    }
117
    delete[] thread_ptr;
118
    for (auto ptr : task_vec) {
119
        delete ptr;
120
    }
121
}
122

123
void TaskSystemParallelThreadPoolSleeping::run(IRunnable* runnable, int num_total_tasks) {
124

125

126
    //
127
    // TODO: CS149 students will modify the implementation of this
128
    // method in Parts A and B.  The implementation provided below runs all
129
    // tasks sequentially on the calling thread.
130
    //
131
    runAsyncWithDeps(runnable, num_total_tasks, std::vector<TaskID>{});
132
    sync();
133
}
134

135
TaskID TaskSystemParallelThreadPoolSleeping::runAsyncWithDeps(IRunnable* runnable, int num_total_tasks,
136
                                                    const std::vector<TaskID>& deps) {
137

138

139
    //
140
    // TODO: CS149 students will implement this method in Part B.
141
    //
142
    std::unique_lock <std::mutex> lock(mtx);
143
    int id = static_cast <int> (task_vec.size());
144
    int pre = 0;
145
    for (const auto &idx : deps) {
146
        Task *ptr = task_vec[idx];
147
        if (ptr->task_done < ptr->task_num) {
148
            pre++;
149
            ptr->suf.push_back(id);
150
        }
151
    }
152
    Task *ptr = new Task(runnable, num_total_tasks, pre);
153
    task_vec.push_back(ptr);
154

155
    if (pre == 0) {
156
        task_que.push(id);
157
        work_cv.notify_all();
158
    }
159

160
    return id;
161
}
162

163
void TaskSystemParallelThreadPoolSleeping::sync() {
164

165
    //
166
    // TODO: CS149 students will modify the implementation of this method in Part B.
167
    //
168
    std::unique_lock <std::mutex> lock(mtx);
169
    sync_cv.wait(lock, [&]() {
170
        return task_done == static_cast<int>(task_vec.size());
171
    });
172
}

评测结果如下

1
katyusha@Katyusha-PC:~/lesson/CS149/asst2/part_b$ python3 ../tests/run_test_harness.py -a
2
runtasks_ref
3
Linux x86_64
4
================================================================================
5
Running task system grading harness... (22 total tests)
6
  - Detected CPU with 16 execution contexts
7
  - Task system configured to use at most 16 threads
8
================================================================================
9
================================================================================
10
Executing test: super_super_light...
11
Reference binary: ./runtasks_ref_linux
12
Results for: super_super_light
13
                                        STUDENT   REFERENCE   PERF?
14
[Serial]                                3.374     3.232       1.04  (OK)
15
[Parallel + Always Spawn]               3.294     143.047     0.02  (OK)
16
[Parallel + Thread Pool + Spin]         3.297     32.456      0.10  (OK)
17
[Parallel + Thread Pool + Sleep]        34.289    49.513      0.69  (OK)
18
================================================================================
19
Executing test: super_super_light_async...
20
Reference binary: ./runtasks_ref_linux
21
Results for: super_super_light_async
22
                                        STUDENT   REFERENCE   PERF?
23
[Serial]                                3.304     3.167       1.04  (OK)
24
[Parallel + Always Spawn]               3.28      141.914     0.02  (OK)
25
[Parallel + Thread Pool + Spin]         3.294     25.471      0.13  (OK)
26
[Parallel + Thread Pool + Sleep]        9.923     49.523      0.20  (OK)
27
================================================================================
28
Executing test: super_light...
29
Reference binary: ./runtasks_ref_linux
30
Results for: super_light
31
                                        STUDENT   REFERENCE   PERF?
32
[Serial]                                43.447    40.952      1.06  (OK)
33
[Parallel + Always Spawn]               43.668    151.303     0.29  (OK)
34
[Parallel + Thread Pool + Spin]         43.431    35.089      1.24  (OK)
35
[Parallel + Thread Pool + Sleep]        60.807    49.644      1.22  (OK)
36
================================================================================
37
Executing test: super_light_async...
38
Reference binary: ./runtasks_ref_linux
39
Results for: super_light_async
40
                                        STUDENT   REFERENCE   PERF?
41
[Serial]                                43.896    40.416      1.09  (OK)
42
[Parallel + Always Spawn]               43.025    149.93      0.29  (OK)
43
[Parallel + Thread Pool + Spin]         43.679    29.589      1.48  (OK)
44
[Parallel + Thread Pool + Sleep]        28.933    24.183      1.20  (OK)
45
================================================================================
46
Executing test: ping_pong_equal...
47
Reference binary: ./runtasks_ref_linux
48
Results for: ping_pong_equal
49
                                        STUDENT   REFERENCE   PERF?
50
[Serial]                                704.422   648.376     1.09  (OK)
51
[Parallel + Always Spawn]               702.252   204.452     3.43  (NOT OK)
52
[Parallel + Thread Pool + Spin]         699.26    156.193     4.48  (NOT OK)
53
[Parallel + Thread Pool + Sleep]        191.514   151.617     1.26  (OK)
54
================================================================================
55
Executing test: ping_pong_equal_async...
56
Reference binary: ./runtasks_ref_linux
57
Results for: ping_pong_equal_async
58
                                        STUDENT   REFERENCE   PERF?
59
[Serial]                                700.791   647.809     1.08  (OK)
60
[Parallel + Always Spawn]               703.253   208.985     3.37  (NOT OK)
61
[Parallel + Thread Pool + Spin]         702.64    156.071     4.50  (NOT OK)
62
[Parallel + Thread Pool + Sleep]        183.948   139.78      1.32  (OK)
63
================================================================================
64
Executing test: ping_pong_unequal...
65
Reference binary: ./runtasks_ref_linux
66
Results for: ping_pong_unequal
67
                                        STUDENT   REFERENCE   PERF?
68
[Serial]                                1291.155  1214.399    1.06  (OK)
69
[Parallel + Always Spawn]               1297.076  265.625     4.88  (NOT OK)
70
[Parallel + Thread Pool + Spin]         1284.404  207.297     6.20  (NOT OK)
71
[Parallel + Thread Pool + Sleep]        262.049   201.473     1.30  (OK)
72
================================================================================
73
Executing test: ping_pong_unequal_async...
74
Reference binary: ./runtasks_ref_linux
75
Results for: ping_pong_unequal_async
76
                                        STUDENT   REFERENCE   PERF?
77
[Serial]                                1292.723  1214.691    1.06  (OK)
78
[Parallel + Always Spawn]               1293.555  263.932     4.90  (NOT OK)
79
[Parallel + Thread Pool + Spin]         1295.538  206.042     6.29  (NOT OK)
80
[Parallel + Thread Pool + Sleep]        258.012   197.771     1.30  (OK)
81
================================================================================
82
Executing test: recursive_fibonacci...
83
Reference binary: ./runtasks_ref_linux
84
Results for: recursive_fibonacci
85
                                        STUDENT   REFERENCE   PERF?
86
[Serial]                                672.702   1059.673    0.63  (OK)
87
[Parallel + Always Spawn]               676.334   144.753     4.67  (NOT OK)
88
[Parallel + Thread Pool + Spin]         671.824   160.962     4.17  (NOT OK)
89
[Parallel + Thread Pool + Sleep]        108.368   139.518     0.78  (OK)
90
================================================================================
91
Executing test: recursive_fibonacci_async...
92
Reference binary: ./runtasks_ref_linux
93
Results for: recursive_fibonacci_async
94
                                        STUDENT   REFERENCE   PERF?
95
[Serial]                                677.219   1065.529    0.64  (OK)
96
[Parallel + Always Spawn]               671.694   141.044     4.76  (NOT OK)
97
[Parallel + Thread Pool + Spin]         672.491   137.377     4.90  (NOT OK)
98
[Parallel + Thread Pool + Sleep]        101.067   134.396     0.75  (OK)
99
================================================================================
100
Executing test: math_operations_in_tight_for_loop...
101
Reference binary: ./runtasks_ref_linux
102
Results for: math_operations_in_tight_for_loop
103
                                        STUDENT   REFERENCE   PERF?
104
[Serial]                                386.117   367.139     1.05  (OK)
105
[Parallel + Always Spawn]               390.633   763.636     0.51  (OK)
106
[Parallel + Thread Pool + Spin]         387.205   155.567     2.49  (NOT OK)
107
[Parallel + Thread Pool + Sleep]        335.568   260.16      1.29  (OK)
108
================================================================================
109
Executing test: math_operations_in_tight_for_loop_async...
110
Reference binary: ./runtasks_ref_linux
111
Results for: math_operations_in_tight_for_loop_async
112
                                        STUDENT   REFERENCE   PERF?
113
[Serial]                                379.027   357.445     1.06  (OK)
114
[Parallel + Always Spawn]               379.425   748.564     0.51  (OK)
115
[Parallel + Thread Pool + Spin]         381.661   129.059     2.96  (NOT OK)
116
[Parallel + Thread Pool + Sleep]        251.303   167.617     1.50  (OK)
117
================================================================================
118
Executing test: math_operations_in_tight_for_loop_fewer_tasks...
119
Reference binary: ./runtasks_ref_linux
120
Results for: math_operations_in_tight_for_loop_fewer_tasks
121
                                        STUDENT   REFERENCE   PERF?
122
[Serial]                                386.693   359.973     1.07  (OK)
123
[Parallel + Always Spawn]               385.614   767.266     0.50  (OK)
124
[Parallel + Thread Pool + Spin]         382.28    195.048     1.96  (NOT OK)
125
[Parallel + Thread Pool + Sleep]        361.556   261.403     1.38  (OK)
126
================================================================================
127
Executing test: math_operations_in_tight_for_loop_fewer_tasks_async...
128
Reference binary: ./runtasks_ref_linux
129
Results for: math_operations_in_tight_for_loop_fewer_tasks_async
130
                                        STUDENT   REFERENCE   PERF?
131
[Serial]                                383.238   362.11      1.06  (OK)
132
[Parallel + Always Spawn]               383.221   748.586     0.51  (OK)
133
[Parallel + Thread Pool + Spin]         383.377   60.354      6.35  (NOT OK)
134
[Parallel + Thread Pool + Sleep]        64.755    95.945      0.67  (OK)
135
================================================================================
136
Executing test: math_operations_in_tight_for_loop_fan_in...
137
Reference binary: ./runtasks_ref_linux
138
Results for: math_operations_in_tight_for_loop_fan_in
139
                                        STUDENT   REFERENCE   PERF?
140
[Serial]                                199.654   185.18      1.08  (OK)
141
[Parallel + Always Spawn]               199.644   111.129     1.80  (NOT OK)
142
[Parallel + Thread Pool + Spin]         200.94    46.147      4.35  (NOT OK)
143
[Parallel + Thread Pool + Sleep]        77.969    56.712      1.37  (OK)
144
================================================================================
145
Executing test: math_operations_in_tight_for_loop_fan_in_async...
146
Reference binary: ./runtasks_ref_linux
147
Results for: math_operations_in_tight_for_loop_fan_in_async
148
                                        STUDENT   REFERENCE   PERF?
149
[Serial]                                200.266   186.405     1.07  (OK)
150
[Parallel + Always Spawn]               196.858   107.224     1.84  (NOT OK)
151
[Parallel + Thread Pool + Spin]         196.916   34.597      5.69  (NOT OK)
152
[Parallel + Thread Pool + Sleep]        32.059    32.355      0.99  (OK)
153
================================================================================
154
Executing test: math_operations_in_tight_for_loop_reduction_tree...
155
Reference binary: ./runtasks_ref_linux
156
Results for: math_operations_in_tight_for_loop_reduction_tree
157
                                        STUDENT   REFERENCE   PERF?
158
[Serial]                                200.065   189.841     1.05  (OK)
159
[Parallel + Always Spawn]               198.557   55.519      3.58  (NOT OK)
160
[Parallel + Thread Pool + Spin]         195.579   36.797      5.32  (NOT OK)
161
[Parallel + Thread Pool + Sleep]        41.008    39.417      1.04  (OK)
162
================================================================================
163
Executing test: math_operations_in_tight_for_loop_reduction_tree_async...
164
Reference binary: ./runtasks_ref_linux
165
Results for: math_operations_in_tight_for_loop_reduction_tree_async
166
                                        STUDENT   REFERENCE   PERF?
167
[Serial]                                196.123   183.502     1.07  (OK)
168
[Parallel + Always Spawn]               195.809   51.347      3.81  (NOT OK)
169
[Parallel + Thread Pool + Spin]         195.512   29.132      6.71  (NOT OK)
170
[Parallel + Thread Pool + Sleep]        34.974    29.707      1.18  (OK)
171
================================================================================
172
Executing test: spin_between_run_calls...
173
Reference binary: ./runtasks_ref_linux
174
Results for: spin_between_run_calls
175
                                        STUDENT   REFERENCE   PERF?
176
[Serial]                                238.154   376.977     0.63  (OK)
177
[Parallel + Always Spawn]               234.787   192.36      1.22  (OK)
178
[Parallel + Thread Pool + Spin]         235.452   236.406     1.00  (OK)
179
[Parallel + Thread Pool + Sleep]        121.11    192.589     0.63  (OK)
180
================================================================================
181
Executing test: spin_between_run_calls_async...
182
Reference binary: ./runtasks_ref_linux
183
Results for: spin_between_run_calls_async
184
                                        STUDENT   REFERENCE   PERF?
185
[Serial]                                242.261   376.192     0.64  (OK)
186
[Parallel + Always Spawn]               235.36    193.519     1.22  (OK)
187
[Parallel + Thread Pool + Spin]         235.4     229.247     1.03  (OK)
188
[Parallel + Thread Pool + Sleep]        121.462   194.465     0.62  (OK)
189
================================================================================
190
Executing test: mandelbrot_chunked...
191
Reference binary: ./runtasks_ref_linux
192
Results for: mandelbrot_chunked
193
                                        STUDENT   REFERENCE   PERF?
194
[Serial]                                296.609   275.69      1.08  (OK)
195
[Parallel + Always Spawn]               295.098   29.164      10.12  (NOT OK)
196
[Parallel + Thread Pool + Spin]         297.117   25.831      11.50  (NOT OK)
197
[Parallel + Thread Pool + Sleep]        25.4      24.446      1.04  (OK)
198
================================================================================
199
Executing test: mandelbrot_chunked_async...
200
Reference binary: ./runtasks_ref_linux
201
Results for: mandelbrot_chunked_async
202
                                        STUDENT   REFERENCE   PERF?
203
[Serial]                                297.946   274.831     1.08  (OK)
204
[Parallel + Always Spawn]               297.743   29.353      10.14  (NOT OK)
205
[Parallel + Thread Pool + Spin]         295.95    24.352      12.15  (NOT OK)
206
[Parallel + Thread Pool + Sleep]        27.117    25.444      1.07  (OK)
207
================================================================================
208
Overall performance results
209
[Serial]                                : All passed Perf
210
[Parallel + Always Spawn]               : Perf did not pass all tests
211
[Parallel + Thread Pool + Spin]         : Perf did not pass all tests
212
[Parallel + Thread Pool + Sleep]        : All passed Perf

Katyusha's blog