几种特殊的平行机上具有前瞻区间的在线分批排序问题的任务书.docx

几种特殊的平行机上具有前瞻区间的在线分批排序问题的任务书
任务书
任务一：基于平行机的在线分批排序问题
问题描述：
在一台平行机上进行在线分批排序，每个分批内的数据都是随时产生的，而且分批之间也是随时到来的，需要实时地对每个分批内的数据进行排序，并将排序结果输出。该平行机有多个处理器，每个处理器都可以处理一个分批，且每个处理器的处理效率不一样，也就是所需的时间不同。每个处理器只能处理一个分批，但是多个处理器可以同时处理多个分批。而且每个分批的大小也不相同，需要根据算法预估每个分批的排序时间，并将分配任务的时间和终止时间告知每个处理器，以避免因任务分配不当而导致的延迟。请设计一个分配策略，以达到尽量节约时间的目的。
要求：
1.分别使用FIFO、最小完成时间和SPT策略，进行实验比较，并分析各自的优缺点；
2.给出算法实现的具体方法和步骤；
3.根据实验结果，给出适宜的分配策略，以避免因任务分配不当而导致的延迟；
4.设计实验数据，分别对300个、600个和900个数据进行实验，并给出实验结果分析报告。
任务二：基于平行机的多源数据合并问题
问题描述：
有10个数据源，每个数据源都是在不同的时间内产生的数据文件，每个数据文件包含10万条记录，每条记录有10个属性。且每个数据文件的记录都是按照某个属性排序的，请在不同的处理器上建立合并索引，将所有数据合并成一个数据文件并按照指定属性排序。该平行机有6个处理器，每个处理器的处理效率不一样，也就是所需的时间不同。每个处理器可以处理一个数据源或者一个合并索引，但是多个处理器可以同时处理多个数据源或者合并索引。请设计一个分配策略，以达到尽量节约时间的目的。
要求：
1.分别使用FIFO、最小完成时间和SPT策略，进行实验比较，并分析各自的优缺点；
2.给出算法实现的具体方法和步骤；
3.根据实验结果，给出适宜的分配策略，以避免因任务分配不当而导致的延迟；
4.设计实验数据，分别对1万条、10万条和100万条数据进行实验，并给出实验结果分析报告。
任务三：基于平行机的实时视频编码问题
问题描述：
在一台平行机上进行实时视频编码，需要把高清视频流压缩成低码率的视频文件，并进行实时传输。该平行机有8个处理器，每个处理器的处理效率不一样，也就是所需的时间不同。请设计一个分配策略，以避免因任务分配不当而导致的延迟。
要求：
1.分别使用FIFO、最小完成时间和SPT策略，进行实验比较，并分析各自的优缺点；
2.给出算法实现的具体方法和步骤；
3.根据实验结果，给出适宜的分配策略，以避免因任务分配不当而导致的延迟；
4.设计实验数据，分别对1分钟、5分钟和10分钟的视频进行实验，并给出实验结果分析报告。
总体要求：
1.采用C/C++或MATLAB等编程语言实现算法，并生成可执行文件；
2.对结果进行分析总结，给出分析报告。