【作者】 王少军；

【导师】 彭喜元；

【作者基本信息】 哈尔滨工业大学 ， 仪器科学与技术， 2012， 博士

【摘要】 时间序列预测作为一种重要的数据分析方法一直受到研究者的广泛关注，然而在很多实际应用中，尤其在越来越多的嵌入式计算资源有限条件下，预测算法的高计算复杂度和庞大的硬件资源消耗成为制约现实应用的瓶颈。作为当前计算模式发展主流方向之一的可重构计算，凭借其定制并行计算的高性能和重构计算的高灵活性，为此问题提供了一种可行的解决方案。因此，将时间序列预测方法与可重构计算相融合，为有限计算资源条件下时间序列预测的高效计算方法研究提供一种新颖的解决思路和基础性的研究框架，具有明显的理论意义和实用价值。目前，从算法层面开展的时间序列预测研究中，尚缺乏对可重构计算适应性的考虑。同时，高复杂度算法的高效计算需求与可重构计算平台中有限的硬件资源也存在直接的矛盾。鉴于此，本文通过比较分析，选择性能优越的最小二乘支持向量机(Least Squares Support Vector Machine, LS-SVM)时间序列预测算法作为本文研究工作的算法基础，从算法的可重构计算适应性改进、资源占用与计算效率平衡的可重构计算方法、以及有限可重构计算资源上的任务调度三个方面，开展时间序列预测的可重构计算方法研究，论文的主要研究工作包括以下内容：（1）针对LS-SVM时间序列预测中存在的算法复杂度高，并且其中的常规线性方程组求解方法不适合可重构计算的问题，提出一种基于聚类的LS-SVM局部建模方法。该方法首先通过低复杂度K-means算法及合理的聚类数确定方法，缩减建模过程样本数量。然后采用改进Cholseky分解方法，实现计算量小且计算稳定性好的线性方程组求解算法。实验结果证明，在可控精度损失条件下，该方法较LS-SVM算法具有更高的训练和预测效率，为后续可重构计算研究提供了合适的算法基础。（2）在LS-SVM算法进行可重构计算适应性改进基础上，针对LS-SVM可重构计算实现中硬件资源占用与计算效率的矛盾问题，提出一种基于部分动态自重构系统的LS-SVM训练过程可重构计算实现方法。该方法在构建部分动态自重构计算系统体系结构基础上，采用时域复用、空域并行的计算结构，实现硬件资源占用与计算效率的平衡。实验结果表明，本文方法可明显提高硬件资源利用率，并具有良好的计算效率。（3）为进一步满足复杂时间序列预测任务的高效计算需求，开展部分动态重构系统静态任务调度方法研究。针对其中存在的重构区划分方法及反碎片技术理想化、配置预取策略被忽视以及最优调度方法计算效率低等问题，在充分研究调度工作机制和最优调度方法的基础上，提出一种基于改进异构最早完成时间表调度方法的启发式算法。该方法在重构区静态划分策略下，以提高利用率和灵活性为原则确定重构区规模，并改进最低水平线法，减少片上布局过程的碎片产生；进而通过积极的配置预取和任务插入，减少配置器和重构区空闲时间。实验结果表明，该调度算法与最优调度算法相比，具有良好的调度性能，同时可以获得明显的运行效率提升。更多还原

【Abstract】 Time series forcasting as a practically useful data analysis method has drawntremendous attentions in scientific research. However, complicated algorithmarchitecture and huge hardware resource occupation have greatly limitedapplications of time series forecasting. Together with increasing applications oftime series forecasting in general embedded systems, efficient forcasting methodsconsuming only restricted hardware resources have become more and morenecessary. As one of the mainstreams in the development of computing,reconfigurable computing(RC) provides a feasible solution to this problem withcustomized high performance parallel computing and flexible reconfiguration.Therefore, the fusion of time series forecasting and RC can provide a novelsolution and basic research framework to the high performance computingresearch of time series forecasting consuming only limited computing resource.So this fusion research has both theoretical and practical significance.Although a number of research works have been proposed to improve thecomputing efficiency of time series forecasting algorithms, applications of RChave surprisingly been ignored in most of these works. Meanwhile, there is anobvious conflict between the efficient computing requirement of complicatedtime series forcasting algorithms and limited RC hardware resources. Given allthese, with careful comparison and analysis, we choose least squares supportvector machine(LS-SVM) as the target algorithms in this paper. Furthermore, wefocus on the RC research of time series forecasting from the perspective of RCapplicability improvement of LS-SVM, RC method with balanced resourceoccupation and computing efficiency, and task scheduling in limited hardwareresources. We here in mainly describe the following work.(1)In LS-SVM based time series forecasting, the high computing complexityand improper linear equations solving method influence its applicability ofreconfigurable computing. To solve this problem, we propose a local modelingmethod of LS-SVM based on clustering strategy. Firstly, we adopt K-meansclustering algorithm with reasonable cluster number to get the local modelingsamples and reduces space complexity. Then, modified Cholesky factorization isused to get analytical, stable and low complex solutions of linear equations.Experiments show that CLS-SVM could obtain better training and predictionefficiency compared to LS-SVM with acceptable precision drop. Moreover, it can reduce the space complexity and get analytical, stable and low complex solutions.All these property make it suitable for reconfigurable computing.(2)To solve the conflict of hardware resources occupation and computingefficiency in the reconfigurable computing of LS-SVM, we propose an LS-SVMreconfigurable computing method based on partial dynamic self-reconfigurablesystem. First we present partial dynamical self-reconfigurable systemarchitecture. Then we propose a time multiplexing and spacial parallel computingstructure to balance the hardware resource occupation and computing efficiency.Experiment results show that when compared to non-time multiplexingarchitecture, our method has high hardware utilization while achieving highcomputing efficiency. This makes the embedded application of LS-SVM withrestricted hardware resources possible.(3)To realize efficient time series forecasting with RC, we explore the taskscheduling in FPGA based partial dynamic RC system. To solve the existingproblems including improper assumptions in reconfigurable partition(RP)divisionmethods and anti-fragments technology, ignorance of configuration prefetch andlow efficiency in optimized scheduling method, with careful study of schedulingmechanism and optimal scheduling method, we propose a heuristic based ontypical heterogeneous multi-core system list scheduling method. With staticdivision strategy of RP, RP sizes are decided under the principle of improvingflexibility and resources utilization. Then chip layout is realized with modifiedminimum horizontal method to reduce fragments. Finally, by active configurationprefetch and task insertion under the limit of serial configuration, we improve thescheduling performance. Simulation experiments and real world application toCLS-SVM algorithm all show that, our heuristic method has a good schedulingperformance and generality. Meanwhile, our heuristic also achieves an obviousefficiency improvement compared to optimal scheduling algorithm.更多还原