Algorithm Research Of Software/Hardware Codeign Optimization On Reconfigurable MPSoC

Reconfigurable Computing (RC) technology, integrates the advantages of both general and custom computing, providing flexible and efficient computing ability. Multi Processor System on Chip (MPSoC), which integrates many function units on the single chip, meets diverse application requirements. RC-MPSoC, a combination of above has computing flexibility and operation efficiency, which makes full use of multi-core computing resources advantages; using hardware programmability, more effectively meets the demand of different embedded applications.The above systems also face many challenges in the design and application field. The flexibility of application and the kernel polymorphism are very difficult to construct the normalized abstraction model; the partitioning, scheduling, and assignment, which brought by the efficiency of hardware acceleration, have been generally considered or proved as a NP-Complete or NP-Hard problem; the feature of reconfigurable resources time-sharing multiplexing add many constraint conditions of management, placement and fragment. So, the research on the codesign optimization algorithm of RC with MPSoC is very significant in the fields of improving system operation performance, enhancing application reliability, and so on.This dissertation mainly focuses on the RC with MPSoC software/hardware codesign application. The object is to optimize computing performance. First, abstract the basic frame structure of MPSoC and RC-MPSoC, and conclude the critical factors which affected the improvement of system performance. Second, with the research status both home and abroad, the corresponding optimization algorithms were given progressively. Last, the space/time complexity of algorithms and the effect on the system performance improvement were analyzed.The main work and features embodied in the following aspects:1. On the foundation of analyzing two state-of-the-art systems platforms of MPSoC and RC-MPSoC both home and abroad, the basic unify frame structure was built, combing with polymorphism calculation and the characters of next generation general processor platform. At the same time, considering the input task type on the platform, major limitation factors and performance improvement objectives, consistent constraint conditions and optimization model was abstracted.2. For software/hardware codesign optimization of MPSoC, based on the analyzing of tasks dependencies, communication cost, processor allocation and other restrictions, we put forward greedy partitioning and insert scheduling (GPISM) codesign optimization algorithm. By using greedy partitioning, the critical hardware path and longest software path were selected; On the basis of system constraints and optimization objects, the rest scattered tasks were inserted into the corresponding processor cores. The time complexity of algorithm is polynomial level, with smaller space overhead.3. For time-sharing multiplexing character of Reconfigurable Computing, based on the analyzing of the restrictions of resource management, placement manner and the fragments measuring, which effected system performance and resource utilization and so on, The VHF hardware placement and management strategy was put forward. The strategy included:the VPT (Vertex Positions Tree) data structure, which reduced storage costs; the HWC (High Weight Corner occupied first) placement manner and clever jump search methods, which reduced the computing time overhead; the FSE (Fragment Shape Edge) measure function, which reduced the computation cost. To solve the effection of permanent fault, the FT-VHF fault tolerant strategy had also been put forward based on the above. Both the VHF and FT-VHF strategies achieved effective resource utilization and low-cost system reliability with lower complexity of time and space.4. For the online and offline task characteristics, the two task scheduling algorithms VHF-Online and VHF-Offline had been put forward, on the basis of analyzing the restrictions of deadline, task dependencies etc. in RC-MPSoC codesign optimization. Combined with the VHF hardware resource management and placement strategy, the above two scheduling algorithms achieved the software/hardware codesign optimization. Using greedy queue scheduling and dynamic priority updating, the VHF-Online algorithm achieved higher rate of tasks acceptance; Eliminating task dependencies with loop iteration, giving the different task hardware/software execution priorities, integrating dynamic partitioning, placement judgment and priority scheduling etc. policies, the VHF-Offline algorithm achieved shorter total scheduling length.