找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索

[ JAVA开发技术 ] 【守望者 j2se】初探Fork/Join并行计算

2014-10-12 13:40| 发布者: zhouy | 查看: 945 | 收藏

摘要: 当硬件处理能力不能按摩尔定律垂直发展的时候,选择了水平发展。多核处理器已广泛应用,未来处理器的核心数将进一步发布,甚至达到上百上千的数量。而现在很多的应用程序在运行在多核心的处理器上并不能得到很好的性 ...
当硬件处理能力不能按摩尔定律垂直发展的时候,选择了水平发展。多核处理器已广泛应用,未来处理器的核心数将进一步发布,甚至达到上百上千的数量。而现在很多的应用程序在运行在多核心的处理器上并不能得到很好的性能提升,因为应用程序的并发处理能力不强,不能够合理有效地的利用计算资源。线性的计算只能利用n分之一的计算支援。


要提高应用程序在多核处理器上的执行效率,只能想办法提高应用程序的本身的并行能力。常规的做法就是使用多线程,让更多的任务同时处理,或者让一部分操作异步执行,这种简单的多线程处理方式在处理器核心数比较少的情况下能够有效地利用处理资源,因为在处理器核心比较少的情况下,让不多的几个任务并行执行即可。但是当处理器核心数发展很大的数目,上百上千的时候,这种按任务的并发处理方法也不能充分利用处理资源,因为一般的应用程序没有那么多的并发处理任务(服务器程序是个例外)。所以,只能考虑把一个任务拆分为多个单元,每个单元分别得执行最后合并每个单元的结果。一个任务的并行拆分,一种方法就是寄希望于硬件平台或者操作系统,但是目前这个领域还没有很好的结果。另一种方案就是还是只有依靠应用程序本身对任务经行拆封执行。


Fork/Join框架


依靠应用程序本身并行拆封任务,如果使用简单的多线程程序的方法,复杂度必然很大。这就需要一个更好的范式或者工具来代程序员处理这类问题。Java 7也意识到了这个问题,才标准库中集成了由Doug Lea开发的Fork/Join并行计算框架。通过使用 Fork/Join 模式,软件开发人员能够方便地利用多核平台的计算能力。尽管还没有做到对软件开发人员完全透明,Fork/Join 模式已经极大地简化了编写并发程序的琐碎工作。对于符合 Fork/Join 模式的应用,软件开发人员不再需要处理各种并行相关事务,例如同步、通信等,以难以调试而闻名的死锁和 data race 等错误也就不会出现,提升了思考问题的层次。你可以把 Fork/Join 模式看作并行版本的 Divide and Conquer 策略,仅仅关注如何划分任务和组合中间结果,将剩下的事情丢给 Fork/Join 框架。但是Fork/Join并行计算框架,并不是银弹,并不能解决所有应用程序在超多核心处理器上的并发问题。


如果一个应用能被分解成多个子任务,并且组合多个子任务的结果就能够获得最终的答案,那么这个应用就适合用 Fork/Join 模式来解决。其原理如下图。


应用程序开发者需要做的就是拆分任务并组合每个子任务的中间结果,而不用再考虑线程和锁的问题。


我们首先看一个简单的Fork/Join的任务定义。

public class Calculator extends RecursiveTask<Integer> {  
  
    private static final int THRESHOLD = 100;  
    private int start;  
    private int end;  
  
    public Calculator(int start, int end) {  
        this.start = start;  
        this.end = end;  
    }  
  
    @Override  
    protected Integer compute() {  
        int sum = 0;  
        if((start - end) < THRESHOLD){  
            for(int i = start; i< end;i++){  
                sum += i;  
            }  
        }else{  
            int middle = (start + end) /2;  
            Calculator left = new Calculator(start, middle);  
            Calculator right = new Calculator(middle + 1, end);  
            left.fork();  
            right.fork();  
  
            sum = left.join() + right.join();  
        }  
        return sum;  
    }  
  
}  

这段代码中,定义了一个累加的任务,在compute方法中,判断当前的计算范围是否小于一个值,如果是则计算,如果没有,就把任务拆分为连个子任务,并合并连个子任务的中间结果。程序递归的完成了任务拆分和计算。任务定义之后就是执行任务,Fork/Join提供一个和Executor框架 的扩展线程池来执行任务。


public void run() throws Exception{  
    ForkJoinPool forkJoinPool = new ForkJoinPool();  
    Future<Integer> result = forkJoinPool.submit(new Calculator(0, 10000));  
  
    assertEquals(new Integer(49995000), result.get());  
}  

Fork/Join框架的主要类 


RecursiveAction供不需要返回值的任务继续。
RecursiveTask通过泛型参数设置计算的返回值类型。
ForkJoinPool提供了一系列的submit方法,计算任务。ForkJoinPool默认的线程数通过Runtime.availableProcessors()获得,因为在计算密集型的任务中,获得多于处理性核心数的线程并不能获得更多性能提升。

public <T> ForkJoinTask<T> submit(ForkJoinTask<T> task) {
    doSubmit(task);
    return task;
}
sumit方法返回了task本身,ForkJoinTask实现了Future接口,所以可以通过它等待获得结果。

这个例子并行排序数组,不需要返回结果,所以继承了RecursiveAction。

public class SortTask extends RecursiveAction {  
    final long[] array;  
    final int start;  
    final int end;  
    private int THRESHOLD = 100; //For demo only  
  
    public SortTask(long[] array) {  
        this.array = array;  
        this.start = 0;  
        this.end = array.length - 1;  
    }  
  
    public SortTask(long[] array, int start, int end) {  
        this.array = array;  
        this.start = start;  
        this.end = end;  
    }  
  
    protected void compute() {  
        if (end - start < THRESHOLD)  
            sequentiallySort(array, start, end);  
        else {  
            int pivot = partition(array, start, end);  
            new SortTask(array, start, pivot - 1).fork();  
            new SortTask(array, pivot + 1, end).fork();  
        }  
    }  
  
    private int partition(long[] array, int start, int end) {  
        long x = array[end];  
        int i = start - 1;  
        for (int j = start; j < end; j++) {  
            if (array[j] <= x) {  
                i++;  
                swap(array, i, j);  
            }  
        }  
        swap(array, i + 1, end);  
        return i + 1;  
    }  
  
    private void swap(long[] array, int i, int j) {  
        if (i != j) {  
            long temp = array;  
            array = array[j];  
            array[j] = temp;  
        }  
    }  
  
    private void sequentiallySort(long[] array, int lo, int hi) {  
        Arrays.sort(array, lo, hi + 1);  
    }  
}  

public void run() throws InterruptedException {  
    ForkJoinPool forkJoinPool = new ForkJoinPool();  
    Random rnd = new Random();  
    long[] array = new long[SIZE];  
    for (int i = 0; i < SIZE; i++) {  
        array = rnd.nextInt();  
    }  
    forkJoinPool.submit(new SortTask(array));  
  
    forkJoinPool.shutdown();  
    forkJoinPool.awaitTermination(1000, TimeUnit.SECONDS);  
  
    for (int i = 1; i < SIZE; i++) {  
        assertTrue(array[i - 1] < array);  
    }  
}  


本文由守望者watchmen收集整理,部分内容源于网络。本文仅代表作者个人观点,不代表守望者的本意。如有违法侵权内容,请提交到守望者管理员处,立即处理。

推荐阅读

【守望者  j2se】ConcurrentHashMap原理分析
【守望者 j2se】ConcurrentHashMap原
集合是编程中最常用的数据结构。而谈到并发,几乎总是离不开集合这类高级数据
【守望者  j2se】双向链表模拟
【守望者 j2se】双向链表模拟
我们熟悉了java单向链表的模拟,现在我就必须开始双向链表的模拟的.1.基础结构
【守望者 高并发】现有高并发WEB服务器 lighttpd Apache Nginx比较
【守望者 高并发】现有高并发WEB服务器
lighttpd网络服务器基于的Lighttpd的网络服务器具有这样的特点:占用内存资源
【守望者 高并发】C10K/C500K与I/O框架
【守望者 高并发】C10K/C500K与I/O框架
C10K、C/500K问题C10K 的意思是10000并发请求,C500K意思是500 000并发请求,
【守望者  JMM】理解volatile内存语义
【守望者 JMM】理解volatile内存语义
理解volatile变量对写多线程程序还是很有帮助的,这样就会避免一上来就是syn这
【守望者  j2se】虚拟机各部分内存溢出情况
【守望者 j2se】虚拟机各部分内存溢出
通过简单的小例子程序,演示java虚拟机各部分内存溢出情况:(1).java堆溢出:
【守望者 高并发】使用CAS实现高效并发处理
【守望者 高并发】使用CAS实现高效并发
守望者:在并发处理应用中,一般使用锁的方式来解决竞争问题,但锁的效率比较
【守望者  j2se】吃透 java I/O 工作机制-1
【守望者 j2se】吃透 java I/O 工作机
I/O 问题可以说是当今互联网 Web 应用中所面临的主要问题之一,因为当前在这
【守望者 大数据】Mahout学习路线图
【守望者 大数据】Mahout学习路线图
Hadoop家族产品,常用的项目包括Hadoop, Hive, Pig, HBase, Sqoop, Mahout, Z
【守望者 j2se】ConcurrentMap之putIfAbsent(key,value)用法讨论
【守望者 j2se】ConcurrentMap之putIfA
先看一段代码:public class Locale { private final static MapString, Lo
【守望者  javascript】判断IE浏览器世界上最短的代码
【守望者 javascript】判断IE浏览器世
最短的IE判定var ie=!-分析以前最短的IE判定借助于IE不支持垂直制表符的特性
【守望者 大数据】机器学习已成为大数据的基石
【守望者 大数据】机器学习已成为大数
机器学习(Machine Learning, ML)是一门多领域交叉学科,涉及概率论、统计学、
【守望者  j2se】多线程与并发知识点总结
【守望者 j2se】多线程与并发知识点总
对于多线程和并发编程这个比较大的技术模块,我们会整理一些帖子方便知识点的
【守望者  j2se】二叉树模拟
【守望者 j2se】二叉树模拟
接着我们就要写一个比较复杂的数据结构的,但是这个数据结构是很重要的,假如
【守望者 SRS  】SRS 源代码分析笔记(0.9.194)-分析服务器对端口的监听 ...
【守望者 SRS 】SRS 源代码分析笔记(
第一部分 分析服务器对端口的监听 端口监听与初始化(一)全局变量_srs_confi

行业聚焦  面试交流  职位推荐  开发视频   技术交流  腾讯微博  新浪微博

友情链接:课课家教育  阿里云  鲜果  W3Cfuns前端网  中国企业家  环球企业家  投资界  传媒梦工场  MSN中文网  Android开发者社区  cnbeta  投资中国网  又拍云存储  美通说传播  IT茶馆  网商在线  商业评论网  TechOrange  IT时代周刊  3W创新传媒  开源中国社区  二维工坊  Iconfans  推酷  智能电视网  FreeBuf黑客与极客  财经网  DoNews  凤凰财经  新财富  eoe移动开发者社区  i黑马  网易科技  新浪科技  搜狐IT  创业家  创业邦  腾讯财经  福布斯中文网  天下网商  TechWeb  雷锋网  新浪创业  和讯科技  品途O2O  极客公园  艾瑞网  抽屉新热榜  卖家网  人民网通信频道  拉勾网  创新派  简单云主机  

手机版|黑名单|守望者在线 在线教育 linux 高级程序设计 C/C++ 大数据 ( 蜀ICP备14029946号

成都守望者科技有限公司 © 2013-2016 All Rights Reserved