是否有任何算法使其链接列表的并行排序值得？

众所周知,Merge Sort是用于排序链表的最佳算法.

大多数合并排序都是根据数组来解释的,每一半都是递归排序的.这将使并行化变得微不足道:独立地对每一半进行排序然后合并两半.

但链表没有"中途"点; 链表一直持续到结束:

头→[a]→[b]→[c]→[d]→[e]→[f]→[g]→[h]→[i]→[j]→...

我现在已经执行了一次实现以获得计数,然后递归地分割计数,直到我们将节点与它进行比较NextNode.递归负责记住两半的位置.

这意味着链表的MergeSort在列表中线性前进.由于它似乎要求通过列表线性进展,我认为它不能并行化.我能想象的唯一方法是:

• 走一下列表来统计 O(n)
• 走到列表的一半,到达中途点 O(n/2)
• 然后排序每一半 O(n log n)

但即使我们在单独的线程中并行排序(a,b)和(c,d),我也会认为NextNode重新排序期间的错误共享会破坏任何并行化的优点.

有没有用于排序链表的并行算法？

数组合并排序算法

以下是对数组执行合并排序的标准算法:

algorithm Merge-Sort
    input:
        an array, A (the values to be sorted)
        an integer, p (the lower bound of the values to be sorted)
        an integer, r (the upper bound of the values to be sorted)

    define variables:
        an integer, q (the midpoint of the values to be sorted)

    q …

我目前正在使用OpenMP进行矩阵计算.我的代码中有几个循环,而是调用每个循环#pragma omp parallel for [...](创建所有线程并在之后销毁它们)我想在开头创建所有这些,并且在程序结束时删除它们以避免开销.我想要的东西:

#pragma omp parallel
{
    #pragma omp for[...]
    for(...)

    #pragma omp for[...]
    for(...)
}

问题是我有一些部分必须只由一个线程执行,但是在一个循环中,它包含那些必须并行执行的循环......这就是它的样子:

//have to be execute by only one thread
int a=0,b=0,c=0;
for(a ; a<5 ; a++)
{

    //some stuff

    //loops which have to be parallelize
    #pragma omp parallel for private(b,c) schedule(static) collapse(2)
    for (b=0 ; b<8 ; b++);
        for(c=0 ; c<10 ; c++)
        {
            //some other stuff
        }

    //end of the parallel zone
    //stuff to be execute by only one thread

} …

我使用aync.parallel并行运行两个函数.这些函数请求RSS提要.然后解析RSS提要并将其添加到我的网页.

但由于某种原因async.parallel运行回调方法而不等到两个函数完成

文件说:

任务完成后,结果将作为数组传递给最终回调.

我的代码.

require('async').parallel([ function(callback) {
        fetchRss(res, bbcOpts); // Needs time to request and parse
        callback();
    }, function(callback) {
        // Very fast.
        callback();
    } ], function done(err, results) {
        if (err) {
            throw err;
        }
        res.end("Done!");
    });

事实上我只有"完成!" 在我的网页上.为什么？

我为什么需要打电话res.end()？

在Node.js的文件说:

必须在每个响应上调用方法response.end().

如果我不打电话,我的网页将被"下载"(我的意思是我的浏览器地址栏中的进度条).

我有一个相当大的对象列表,我想并行应用一个复杂的函数,但我当前的方法使用了太多的内存.我认为引用类可能会有所帮助,但使用mcapply它们来修改它们似乎不起作用.

该函数修改了对象本身,因此我用新的对象覆盖原始对象.由于该对象是一个列表,我只修改了它的一小部分,我希望R的复制修改语义可以避免生成多个副本; 然而,在运行它时,似乎并不是我正在做的事情.这是我一直使用的基本R方法的一个小例子.它正确地将余额重置为零.

## make a list of accounts, each with a balance
## and a function to reset the balance
foo <- lapply(1:5, function(x) list(balance=x))
reset1 <- function(x) {x$balance <- 0; x}
foo[[4]]$balance
## 4 ## BEFORE reset
foo <- mclapply(foo, reset1)
foo[[4]]$balance
## 0 ## AFTER reset

似乎使用引用类可能会有所帮助,因为它们是可变的,并且在使用lapply它时确实按照我的预期进行; 余额重置为零.

Account <- setRefClass("Account", fields=list(balance="numeric"),
                       methods=list(reset=function() {balance <<- 0}))

foo <- lapply(1:5, function(x) Account$new(balance=x))
foo[[4]]$balance
## 4
invisible(lapply(foo, function(x) x$reset()))
foo[[4]]$balance
## 0

但是当我使用时mclapply,它没有正确重置.请注意,如果您使用的是Windows …

我有一项服务,我必须在从API获取后将大量记录保存到数据库.同时我必须将这些记录从服务返回给调用者.但问题是我在DB中保存记录需要很长时间,因此服务变慢.我搜索了这个并发现了一些并行任务或异步等待的概念.

我是这个概念的新手,对它的用法感到困惑

我调查了一下:

运行多个C#任务异步 http://msdn.microsoft.com/en-us/library/hh191443.aspx

但我不知道该怎么办.请帮助我:

下面是代码:

public List<SearchedItems> SearchItems(string ItemToSearch, string AuthenticationToken)
{
    var _list= getRecords from Api //100 records    

     //Task<int>.Factory.StartNew(() => _objBLLNutritionLog.FillNutritionTable(_tempList)); // also tried this

    saveToDb(_list); // need to run this asynchronously Or parallel (Taking long time)

    return _list;

}

我想将结果返回给调用者,另一方面想要填充db.请建议.

谢谢

我有一个大型并行(使用MPI)模拟应用程序,它可以生成大量数据.为了评估这些数据,我使用了一个python脚本.

我现在需要做的是运行此应用程序很多次(> 1000)并从结果数据计算统计属性.

到目前为止,我的方法是,使用并行运行的python脚本(使用mpi4py,使用即48个节点)调用模拟代码subprocess.check_call. 我需要这个调用来串行运行我的mpi模拟应用程序. 在这种情况下,我不需要模拟并行运行.然后,python脚本可以并行分析数据,并在完成后将启动新的模拟运行,直到累积大量运行.

目标是

• 不保存2000次运行的整个数据集
• 将中间数据保存在内存中

Stub MWE:

档案multi_call_master.py:

from mpi4py import MPI
import subprocess

print "Master hello"

call_string = 'python multi_call_slave.py'

comm = MPI.COMM_WORLD

rank = comm.Get_rank()
size = comm.Get_size()

print "rank %d of size %d in master calling: %s" % (rank, size, call_string)

std_outfile = "./sm_test.out"
nr_samples = 1
for samples in range(0, nr_samples):
    with open(std_outfile, 'w') as out:
        subprocess.check_call(call_string, shell=True, stdout=out)
#       analyze_data()
#       communicate_results()

file multi_call_slave.py(这将是C模拟代码):

from mpi4py …

下面是我的问题的MWE:我已经使用引导程序(通过引导程序包中的引导功能)为某些功能编写了进度条.

只要我不使用并行处理(res_1core下面),这样就可以正常工作.如果我想通过设置parallel = "multicore"和使用并行处理ncpus = 2,则进度条显示不正确(res_2core如下).

library(boot)

rsq <- function(formula, data, R, parallel = c("no", "multicore", "snow"), ncpus = 1) {
  env <- environment()
  counter <- 0
  progbar <- txtProgressBar(min = 0, max = R, style = 3)
  bootfun <- function(formula, data, indices) {
    d <- data[indices,]
    fit <- lm(formula, data = d)
    curVal <- get("counter", envir = env)
    assign("counter", curVal + 1, envir = env)
    setTxtProgressBar(get("progbar", envir = env), curVal + …

我有一个四核i7 920 CPU.它是超线程的,因此计算机认为它有8个核心.

从我在interweb上看到的,在执行并行任务时,我应该使用物理内核的数量,而不是超线程内核的数量.

所以我做了一些时间,并且惊讶地发现在并行循环中使用8个线程比使用4个线程更快.

为什么是这样？我的示例代码太长了,无法在此处发布,但可以通过运行以下示例找到:https://github.com/jsphon/MTVectorizer

性能图表在这里:

我试图围绕如何使用GCD来并行化和加速蒙特卡罗模拟.大多数/所有简单示例都是针对Objective C提供的,我真的需要一个Swift的简单示例,因为Swift是我的第一个"真正的"编程语言.

Swift中蒙特卡罗模拟的最小工作版本将是这样的:

import Foundation

import Cocoa
var winner = 0
var j = 0
var i = 0
var chance = 0
var points = 0
for j=1;j<1000001;++j{
    var ability = 500

    var player1points = 0

    for i=1;i<1000;++i{
        chance = Int(arc4random_uniform(1001))
        if chance<(ability-points) {++points}
        else{points = points - 1}
    }
    if points > 0{++winner}
}
    println(winner)

代码可以直接粘贴到xcode 6.1中的命令行程序项目中

最内层的循环不能并行化,因为变量"points"的新值在下一个循环中使用.但最外面的只是运行最里面的模拟1000000次并计算结果,应该是并行化的理想候选者.

所以我的问题是如何使用GCD并行化最外层的for循环？

我正在阅读Peter S. Pacheco 对并行编程的介绍.在5.6.2节中,它提供了一个关于减少fork/join开销的有趣讨论.考虑奇偶换位排序算法:

for(phase=0; phase < n; phase++){
    if(phase is even){
#       pragma omp parallel for default(none) shared(n) private(i)
        for(i=1; i<n; i+=2){//meat}
    }
    else{
#       pragma omp parallel for default(none) shared(n) private(i)
        for(i=1; i<n-1; i+=2){//meat}
    }
}

作者认为上面的代码有一些高的fork/join开销.因为线程在外循环的每次迭代中分叉并连接.因此,他提出以下版本:

# pragma omp parallel default(none) shared(n) private(i, phase)
for(phase=0; phase < n; phase++){
    if(phase is even){
#       pragma omp for
        for(i=1; i<n; i+=2){//meat}
    }
    else{
#       pragma omp for
        for(i=1; i<n-1; i+=2){//meat}
    }
}

根据作者的说法,第二个版本在外部循环开始之前分叉线程,并为每次迭代重用线程,从而产生更好的性能.

但是,我怀疑第二个版本的正确性.在我的理解中,#pragma omp parallel指令启动一组线程并让线程并行执行以下结构化块.在这种情况下,结构化块应该是整个外部for循环 …