【摘 要】
：
随着大数据时代的到来,数据存储量已从常见的TB上升为NB,1NB为260TB,在大数据商业价值备受关注的今天,海量数据的挖掘、分析、存储等问题都给计算机系统性能带来巨大挑战。Map Reduce系统的出现为大数据快速处理带来了可能,它是一种面向大规模数据处理的并行运算模型和方法。本文研究了Map Reduce同顺序作业排序极小化最大完工时间问题,全文共分四章。第1章简单介绍了经典排序问题的基本知识
论文部分内容阅读
随着大数据时代的到来,数据存储量已从常见的TB上升为NB,1NB为260TB,在大数据商业价值备受关注的今天,海量数据的挖掘、分析、存储等问题都给计算机系统性能带来巨大挑战。Map Reduce系统的出现为大数据快速处理带来了可能,它是一种面向大规模数据处理的并行运算模型和方法。本文研究了Map Reduce同顺序作业排序极小化最大完工时间问题,全文共分四章。第1章简单介绍了经典排序问题的基本知识和Map Reduce编程模型基本框架。第2章主要研究了Map Reduce框架下F2|MapReduce|Cmax排序问题。在这里,工件由map任务和reduce任务构成,map任务可以并行加工,而reduce任务不能并行加工。每个工件的reduce任务又分成m道工序,分别在m台速度相同的机器上加工,每道工序须等其前一工序结束后开始加工,而第一道工序要等其工件的map任务完全加工完后才可开始加工。首先考虑了m=2时,若工件map任务大于reduce任务,则问题是多项式时间可解的,MRJ算法为最优算法。第3章主要是对reduce任务加工工序大于两道时的分析。当工件map任务加工时间为0时,该问题多项式归结为Fm||Cmax问题,在经典排序模型中,Fm||Cmax是强NP-hard的,容易得出问题Fm|MapReduce|Cmax也是强NP-hard的,由分析得出,对问题的MRA算法,其最坏情况界为2-1/m,并且这个界是紧的,其中m是机器台数。第4章对文中所研究的问题进行了总结,进一步展望以后的研究工作。
其他文献
随着当今科技的快速发展,人们对智能家居的智能化需求越来越高。近年来人们对脑机接口（Brain Computer Interface,BCI）技术以及脑电信号（Electroencephalogram,EEG）的研究已取得了一些实际成果。如何实现家居设备的“脑电波”控制,这是当今智能家居一个新的研究方向。只有将BCI技术真正应用到智能家居系统,将人的“意念控制”在智能家居系统中准确地体现,才能更好地
随着现代无线通信技术飞速发展,通信系统对微波无源器件的要求越来越高,为了满足通信系统的不同需求,需要不断对微波无源器件进行优化设计。为了提高微波无源器件的设计效率,降低设计的时间成本,利用算法对其进行设计已经成为一种必然趋势。机器学习是一种简单、快速建立映射关系的方法,但是由于需要大量样本进行训练,导致其在实际应用中时间复杂度较高。论文以提高微波滤波器和天线设计效率为出发点,开展了基于极限学习机（
分裂可行问题（Split Feasibility Problem）是最优化领域中一类十分常见而又重要的问题.在医学、信号处理、图像重建以及压缩传感等工程技术领域有着广泛的应用.从问题提出至今,国内外的众多学者对其进行分析和研究,并提出了许多关于这一问题的算法.随着对分裂可行问题研究的更加深入,专家学者们从不同的角度对分裂可行问题及其相关的优化问题进行研究,分裂可行问题的最小范数解便是其中之一.目前
本文我们在L2（R+）中考虑由方程-y"+[p（x）+2λq（x）]y=λ2y,x∈R+=[0,+∞)和边界条件y’/y（0）=β1λ+βo/α1λ+αo生成的带有二次束的Schr（?）dinger算子L（λ）的谱结构,其中p（x）和q（x）是复值函数,α0,α1,β0,β1是复数并且α0/β1-α1β0≠0.证明了在条件p（x）,q’（x）∈AC（R1）,limx→∞[|p（x）|+|q（x）|
青头潜鸭（Aythya baeri）成年个体的数量已不足1000只,其种群数量受到严重威胁,是世界最濒危的鸟类之一。主要组织相容性复合体（Major histocompatibility complex,MHC）是脊椎动物最具多态性的基因家族之一,在对病原体的免疫防御中发挥重要作用,其能反应一个物种对环境的适应能力。为了调查维持青头潜鸭、斑背潜鸭、凤头潜鸭和红头潜鸭MHC I类基因多态性的机制,我
随着科学技术的进步,智能机器人产业得到了快速发展,并逐渐应用于各大行业。机械臂是机器人的重要执行机构,机器人取代人工完成的各项任务均由机械臂完成,因此机器人的发展,可以说是取决于机械臂的发展。为解决六自由度机械臂系统逆向运动学求解复杂、路径规划算法耗时、精准动力学模型未知、运动过程中存在较多干扰等问题。本文基于瑞士生产的Personal Robotics（P-Rob）六自由度机械臂进行了系统的理论
非线性系统的控制设计和稳定性分析广泛应用于实际工业系统,如电力系统、航天系统、机器人系统和生物化学系统等,并且一直是控制理论领域研究的热点和难点.磁悬浮系统作为一类典型的非线性系统,因其良好的性能在发电机、卫星姿态控制等领域得到了广泛的应用.系统运行的稳定性和安全性是首要考虑的重要因素,有限时间稳定较渐近稳定具有更好的鲁棒性和抗干扰性能.此外,受到外界条件及系统本身结构的限制,磁悬浮系统在运行过程
随着经济转型升级和城市化进程的加快,我国城市发展模式已由蔓延式的增量扩充向内涵式的存量发展转化,早期批建于城郊的工业建筑已成为各级城市的中心构成,如何正确对待这些低效使用甚至早已废弃的工业资源,已成为判定城市经济、文化、社会、环境综合协调发展与全面复兴的关键。论文以枣庄市天鹅地毯厂的保护与再利用设计为研究课题,以枣庄市城市规划、文创产业发展等上位法规决策为设计指导,通过文献查阅、案例分析、问卷调查
在实际生产生活中,时滞现象广泛存在,如网络中信号的传输和处理产生时延,弹性力学中物理变化产生滞后,生物学中传染病存在潜伏期等.另一方面,系统经常遭受来自外界环境的干扰.时滞现象和外部扰动的存在,不仅使系统的分析和综合变得复杂和困难,而且是导致实际控制系统品质恶化和不稳定的重要因素.因此,时滞系统的鲁棒控制器设计成为控制领域一项重要的研究课题,近年来涌现了大量的研究成果,其中,基于时滞Hamilto
随着计算机和通信技术的发展,一种新型的大规模资源受限的无线嵌入式控制系统出现在人们的视野.在经典的样本数据控制框架中,无论系统控制是否需要更新,控制器的输出都可以随即应用于系统.然而当网络资源有限问题突出时,这可能并不是最优解决方案.在上述系统中,控制器与传感器之间的信息在必要时进行传递的这一思路促使了事件触发控制的出现.此外,由于事件触发控制不仅可以满足系统性能要求,而且在一定程度上能够节约资源