Report: Frequency Oriented Scheduling on Parallel Processors

The LOIS project aims at building a radio sensor and IT infrastructure in the south of Sweden, primarily with but not limited to the goal of space observations. Signals received produce a gigantic stream of data that has to be processed in real time. The target is to schedule stream computations to computation nodes in such a way that the performance requirements are met.


1. Introduction
1.1 Problem
1.2 Goals
1.3 Outline
2. Background
2.1 The task graph model
2.2 The machine model
2.3 The purpose of scheduling
Method A
Method B
Comparison of Method A and Method B
2.4 The frequency
2.5 The Layerd Task Graph
2.6 The Blank Time
3. The schedule without communication times
3.1 The Basic Algorithm
3.2 The Simplest Case
3.3 A small change in the simplest case
3.4 Different computation cost
3.4.1 Line structure task graph
3.4.2 Send out tree/ Receive tree
3.5 More parallel methods
3.6 Greedy method
3.7 When to use the greedy method
4. Schedule data communication in LogP model
4.1 Thinking in LogP Const
4.1.1 The basic algorithm
4.1.2 The Greedy method
4.2 Thinking in LogP Linear
4.2.1 BasicFO
4.2.2 GreedyMethod
5. Design Part
5.1 DMDA
5.1.1 General architecture of the local schedule environment in DMDA
5.2 The Implementation of the Basic Algorithm
5.3 The Implementation of the Greedy method
5.4 The task graph generators
5.4.1 The extension of the task graph generators
5.5 Provide the LogP machine model
5.6 Diagnosing the algorithm
6. Benchmark
6.1 The Brent
6.2 Performance Score
6.3 Test in fixed computation time task graph
6.4 Random Computation Time 1-100
6.4.1 Different width in Wave task graph
6.5 Random Computation Time 1-1000
6.6 LogPConst
6.7 LogPLinear
6.8 Large Communication Cost
7. Conclusion
8. Future work

Author: Zhong, Siqi

Source: Vaxjo University

Download URL 2: Visit Now

Leave a Comment