Parallel Scheduling And Performance Analyzing Of Real-time Streaming Applications On Multi-Processor Systems-on-Chips

Streaming applications are pervasively used in our daily life,for example,the audio and video encoding/decoding,communication signal processing in software defined radio,graph and image processing and radar signal processing all belong to streaming applications.As the requirements of system performance increases,these applications place more and more burden on platform.To provide sufficient computation capacity and make a good trade-off between energy consumption and design cost,multiprocessor systems-on-chips are widely adopted in implementing these application systems.Since most streaming applications have strict timing requirements,for example,the application latency and/or throughput should meet specific standard,making analyzing the schedule performance of the application on the hardware platform crucial in guaranteeing system performance.Besides,the system performance has tight relation with the application schedule,making it critical to study how to reasonably exploit the hardware resource and better satisfy the system performance requirements.Thus,this dissertation focuses on parallel scheduling and performance analyzing of streaming applications on multiprocessor systems-on-chips,and the main research issues and contributions are as follows.Considering the mapping problem of streaming applications on multiprocessor systemson-chips,this dissertation first proposes a parallel graph model to quantify and model the parallelism among the tasks of the application,designs a self-timed schedule based parallel graph constructing algorithm,and transforms the mapping problem to the partitioning problem of the parallel graph.Based on the parallel graph,the dissertation models the mapping problem as a pure 0-1 inter linear programming model.Since the complexity of the ILP model increases with the size of the application and platform,this dissertation proposes a two-step heuristic algorithm that composes of greedy strategy and refinement.The heuristic algorithm first uses the greedy strategy to obtain the initial mapping,and then gradually refines the parallelism of the mapping by task migration.The experiments show that the proposed algorithms outperform available methods.Considering the problem of analyzing the throughput of parallel schedule of streaming applications,this dissertation proposes a schedule-aware dataflow model based on homogeneous synchronous dataflow graph to model the periodic static order schedule,and proposes the modeling algorithm.By exploiting the structure of the application model and periodic static order schedule,the model size(task number and edge number)and initial token number are reduced;besides,the throughput of proposed model can be analyzed using available throughput analyzing methods.The experiments show that the proposed technique can reduce the throughput analysis time effectively.Considering the multiprocessor platform that uses network-on-chip as the interconnect architecture,this dissertation models the task and communication co-scheduling problem with duplication and mapping constraints as the inter linear programming model,thus solving the optimal scheduling problem of streaming applications.First,for the contention-free scheduling problem,a contention-free ILP model is proposed.The communication schedule on network-on-chip that uses circuit switch and static routing strategy is modeled,and the task schedule on multiprocessors is also modeled.Since communication contention has significant impact on schedule accuracy on systems with communication contention,the contention-free ILP model is extended to improve the accuracy of the schedule and the practicability of the formulation by proposing a contention-aware ILP model,in which extra constraints are added to avoid communication contention of different communication transactions on links of the network-on-chip.The experiments show that the proposed ILP models can improve the schedule performance effectively.Considering the multiprocessor system-on-chip with predictable memory hierarchy,this dissertation at last proposes an Iteration-based Task-FIFO Co-Scheduling framework to solve the task-FIFO co-scheduling problem of streaming applications.Different tasks of the streaming application adopt FIFO to fulfill iter-task communication,and the schedule performance has important relation with the FIFO size,this dissertation proposes using the state space searching and the iteration strategy to optimize the FIFO size.Different memories in the hardware platform differ in size,and each processor has various access speed for different memories,so the FIFO-to-memory allocation has significant impact on schedule performance.This dissertation proposes a global FIFO allocation optimizing algorithm to refine the FIFO allocation by optimizing the global FIFO access cost.To analyze the system performance,a method to model the task and FIFO schedule into the SDFG is proposed,and the state space searching based method is used for throughput analysis.The experiments show that the proposed algorithms outperform available techniques.