MESSAGE
| DATE | 2016-11-14 |
| FROM | Ruben Safir
|
| SUBJECT | Re: [Learn] merge sort in parallel assignment
|
From learn-bounces-at-nylxs.com Mon Nov 14 21:10:22 2016
Return-Path:
X-Original-To: archive-at-mrbrklyn.com
Delivered-To: archive-at-mrbrklyn.com
Received: from www.mrbrklyn.com (www.mrbrklyn.com [96.57.23.82])
by mrbrklyn.com (Postfix) with ESMTP id 98D1E161312;
Mon, 14 Nov 2016 21:10:22 -0500 (EST)
X-Original-To: learn-at-nylxs.com
Delivered-To: learn-at-nylxs.com
Received: from [10.0.0.62] (flatbush.mrbrklyn.com [10.0.0.62])
by mrbrklyn.com (Postfix) with ESMTP id D3B33160E77
for ; Mon, 14 Nov 2016 21:10:20 -0500 (EST)
To: learn-at-nylxs.com
References: <1d19cb98-d071-2914-bf6a-d8e4d3bc81d9-at-mrbrklyn.com>
<87d1hxvomh.fsf-at-contrapunctus.net>
From: Ruben Safir
Message-ID: <5e3531b5-190c-9d3a-c63b-a59fac5c6c08-at-mrbrklyn.com>
Date: Mon, 14 Nov 2016 21:10:20 -0500
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101
Thunderbird/45.4.0
MIME-Version: 1.0
In-Reply-To: <87d1hxvomh.fsf-at-contrapunctus.net>
Subject: Re: [Learn] merge sort in parallel assignment
X-BeenThere: learn-at-nylxs.com
X-Mailman-Version: 2.1.17
Precedence: list
List-Id:
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7bit
Errors-To: learn-bounces-at-nylxs.com
Sender: "Learn"
On 11/14/2016 02:37 PM, Christopher League wrote:
>
> I didn't know about this `std::thread` ... that's a lot easier than
> writing the `pthread` stuff by hand, I guess. Nice selection of the
> names `sinetro` and `dextro`.
I was running out of names. This text I picked up, C++ Concurrency IN
ACTION, Practical Multithreading by Anthony Williams covers the newish
thread lbraries added to C++-11
>
> One piece of advice I've seen for parallel tree algorithms in Haskell is
> that recursing on left/right asynchronously the whole way down the tree
> adds too much overhead.
Yes and I'm sure that is why it bombs when I run it with too large of a
data field for input.
> You want to spawn off threads for maybe the top
> 2-3 layers of subtrees (so 4-8 threads) but then just proceed
> sequentially after that. (You're running on 4-8 cores, so any additional
> threads sitting around waiting are just overhead.)
>
I was considering just that and limiting the thread to 16. I'd need to
write about function that doesn't make threads recursively and replace
it with two other functions, one with serial recursion and the other
that spins off the threads, that calls the recursive one. I'd need to
write a function for each level, actually. Alternately I could create a
global static index that each thread starts up, and stop calling for new
threads when you reach the number you want. Its not perfect, because
threads are in a race condition to read and write to the index, but that
is likely to be of little practical consequence to the program and
currently it bombs with big data.
I can wrap it all up in catch and try.
> CL
>
> Ruben Safir writes:
>
>> So in terms of the HW this is done, although I'm not happy this the
>> code. It errors on me when the merge is too large, likely due to a
>> combination of compile deficiency and my coding not doing enough error
>> checking. It might help to define the standard c++ to 11, but I'm not
>> certain of that. I need some sleep.
>>
>> Reuvain
>>
>> --
>> So many immigrant groups have swept through our town
>> that Brooklyn, like Atlantis, reaches mythological
>> proportions in the mind of the world - RI Safir 1998
>> http://www.mrbrklyn.com
>>
>> DRM is THEFT - We are the STAKEHOLDERS - RI Safir 2002
>> http://www.nylxs.com - Leadership Development in Free Software
>> http://www2.mrbrklyn.com/resources - Unpublished Archive
>> http://www.coinhangout.com - coins!
>> http://www.brooklyn-living.com
>>
>> Being so tracked is for FARM ANIMALS and and extermination camps,
>> but incompatible with living as a free human being. -RI Safir 2013
>> /*
>> * =====================================================================================
>> *
>> * Filename: msort.h
>> *
>> * Description: Header File for Parrell Msort algorthm
>> *
>> * Version: 1.0
>> * Created: 11/09/2016 04:28:51 AM
>> * Revision: none
>> * Compiler: gcc
>> *
>> * Author: Ruben Safir
>> * Company: NYLXS Inc
>> *
>> * =====================================================================================
>> */
>> #ifndef MSORT_INC
>> #define MSORT_INC
>>
>> namespace merge{
>>
>>
>> int min(int x, int y);
>> void track(int , int, int * );
>> void merge(int j, int l, int m, int k, int * parent);
>> }
>> #endif /* ----- #ifndef MSORT_INC ----- */
>>
>> CXX:=g++
>> CXXFLAGS:=-Wall -ggdb -pg -pthread
>>
>> LDFLAGS:=-L/usr/local/lib/mysql -lmysqlpp -lmysqlclient
>>
>> msort : msort.o main.o
>> ${CXX} ${CXXFLAGS} -o msort msort.o main.o
>>
>> main.o : main.cpp
>> ${CXX} ${CXXFLAGS} -o main.o -c main.cpp
>>
>> msort.o : msort.cpp msort.h
>> ${CXX} ${CXXFLAGS} -c msort.cpp
>>
>> clean :
>> rm nodes *.o make.deps
>> touch *.cpp *.h
>>
>> include make.deps
>> make.deps: *.cpp ; gcc -M *.cpp >$-at-
>> #include "msort.h"
>> #include
>> #include
>> namespace merge{
>>
>> int min(int x, int y){
>> int ret;
>> x>> std::cout << x << ":" << y << "==>" << ret << std::endl;
>> return ret;
>> }
>>
>> void merge(int j, int l, int m, int k, int * value){
>> int size = (k-j) + 1;
>> std::cout << "Allocating scratch ==>" << size << std::endl;
>> int * scratch = new int[size];
>> int l_pos1 = j;
>> int l_pos2 = l;
>> int r_pos1 = m;
>> int r_pos2 = k;
>> int i = 0;
>> std::cout << "Scratch index: " << i << std::endl;
>> std::cout << "l_pos1: " << l_pos1 << "\tr_pos1: " << r_pos1 << std::endl;
>> std::cout << "l_pos2: " << l_pos2 << "\tr_pos2: " << r_pos2 << std::endl;
>> int l_next = l_pos1;
>> int r_next = r_pos1;
>> int cur = -1;//cursor rest position
>> int cursor[3] = {cur, l_next, r_next};
>> while((cursor[1] <= l_pos2) && (cursor[2] <= r_pos2)) {
>> std::cout << "Positions" << cursor[0] << ":" << cursor[1] << ":" << cursor[2] << std::endl;
>> std::cout << "Values " << value[cursor[1]] << ":" << value[cursor[2]] << std::endl;
>> if(value[cursor[1]] <= value[cursor[2]]) {
>> scratch[i] = value[cursor[1]];
>> cursor[0] = cursor[1];
>> cursor[1]++;
>> }else if(value[cursor[1]] > value[cursor[2]]){
>> scratch[i] = value[cursor[2]];
>> cursor[0] = cursor[2];
>> cursor[2]++;
>> }
>> std::cout << "Positions" << cursor[0] << ":" << cursor[1] << ":" << cursor[2] << std::endl;
>> std::cout << "Values " << value[cursor[1]] << ":" << value[cursor[2]] << std::endl;
>> i++;
>> }
>> //we hit the top
>> while(1){
>> std::cout << "clearing data...";
>> if(cursor[2] <= r_pos2 ){
>> scratch[i] = value[cursor[2]];
>> i++;
>> cursor[2]++;
>> }else if(cursor[1] <= l_pos2){
>> scratch[i] = value[cursor[1]];
>> i++;
>> cursor[1]++;
>> }else{
>> break;
>> }
>> }
>> std::cout << "done" << std::endl;
>> //copy scratch to the array
>> std::cout << "copying scratch" << std::endl;
>> for(int pos = j, i=0; i <= (k-j); pos++, i++){
>> std::cout << i << " : " << scratch[i] <<" to position " << pos << std::endl;
>> value[pos] = scratch[i];
>> }
>> std::cout << "free scratch" << std::endl;
>> delete[] scratch;
>> std::cout << "done with scratch" << std::endl;
>> return;
>> }
>>
>> //j is far left of array
>> //k is far right of array
>> //l is middle of array - right of left child array
>> //m is middle + 1 of the array - left of right child array
>> //
>> // j l m k
>> //_____________________________________
>> //| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9| 10| 11|
>> //--------------------------------------
>> //
>>
>>
>> void track(int j, int k, int * parent )
>> {
>> //std::cout << "\n j is far left of array\n k is far right of array\n l is middle of array - right of left child array\n m is middle + 1 of the array - left of right child array\n\n j l m k\n _____________________________________\n | 0| 1| 2| 3| 4| 5| 6| 7| 8| 9| 10| 11|\n --------------------------------------\n ";
>>
>> std:: cout << "======================" << std::endl;
>>
>> std::cout << "|| __NEW NODE__ ||\n|| j =>" << j << " " << "k=> " << k << " ||" << std::endl;
>> std:: cout << "======================" << std::endl;
>> int length = k - j;
>> int l = j + (length / 2);
>> int m = l + 1;
>>
>>
>> if(j == k )
>> {
>> std::cout << "\n\n\n**********RETURN**********" << std::endl;
>> return;
>> }
>>
>> std::cout << "Left Branch: j =>" << j << "\t" << "l => " << l << std::endl;
>> std::cout << "Right Branch: m =>" << m << "\t" << "k => " << k << std::endl;
>> std::cout << std::endl;
>> std::cout << std::endl;
>> std::cout << std::endl;
>> std::cout << "***Enter left : j =>" << j << "\t" << "l => " << l << "***" << std::endl;
>> std::thread sinetro( track, j, l, parent ) ;
>> std::cout << "Returned to Node j => " << j << "\tk=> " << k << " From the left" << std::endl;
>> std::cout << std::endl;
>>
>> std::cout << "***Enter right : m =>" << m << "\t" << "k => " << k << std::endl;
>> std::thread dextro( track, m, k, parent);
>> std::cout << "Returned to Node j => " << j << "\tk=> " << k << " From the right" << std::endl;
>> std::cout << "**********MERGE**********" << std::endl;
>> sinetro.join();
>> dextro.join();
>> merge(j,l,m,k, parent);
>>
>> }
>>
>> }//end namespace
>> /*
>> * =====================================================================================
>> *
>> * Filename: main.cpp
>> *
>> * Description: merge sort main
>> *
>> * Version: 1.0
>> * Created: 11/09/2016 09:33:20 AM
>> * Revision: none
>> * Compiler: gcc
>> *
>> * Author: Ruben Safir
>> * Company: NYLXS
>> *
>> * =====================================================================================
>> */
>> #include
>> #include "msort.h"
>> #include
>> #include
>> #include
>> #define SIZE 10000
>>
>> int main(int argv, char **argc)
>> {
>> using namespace std;
>>
>> int *data = new int[SIZE];
>> // int *cache = new int[SIZE];
>> struct timespec now;
>> clock_gettime(CLOCK_REALTIME, &now);
>> long seed = now.tv_nsec;
>> srand( (unsigned int) seed);
>> for(int i = 0; i < SIZE; i++){
>> data[i] = rand() % 1000000;
>> cout << data[i] << "\t";
>> }
>> cout << endl;
>>
>> cout << "________________________________________________________" << endl;
>>
>> cout << "***Size of Array " << SIZE << "****" << endl;
>> cout << "____________________" << endl;
>> cout << "Array Before" << endl;
>> for(int i = 0; i < SIZE; i++){
>> cout << "--------------------" << endl;
>> cout << "| " << i << " ==> " << data[i] << "\t |" << endl;
>> }
>> cout << "--------------------" << endl;
>> cout << "--------------------" << endl;
>>
>>
>> merge::track(0, SIZE - 1, data);
>>
>> cout << "____________________" << endl;
>> cout << "Array AFTER" << endl;
>> for(int i = 0; i < SIZE; i++){
>> cout << "--------------------" << endl;
>> cout << "| " << i << " ==> " << data[i] << "\t |" << endl;
>> }
>> cout << "--------------------" << endl;
>> cout << "--------------------" << endl;
>>
>>
>> return 0;
>>
>> }
>>
>> _______________________________________________
>> Learn mailing list
>> Learn-at-nylxs.com
>> http://lists.mrbrklyn.com/mailman/listinfo/learn
>
>
>
> _______________________________________________
> Learn mailing list
> Learn-at-nylxs.com
> http://lists.mrbrklyn.com/mailman/listinfo/learn
>
--
So many immigrant groups have swept through our town
that Brooklyn, like Atlantis, reaches mythological
proportions in the mind of the world - RI Safir 1998
http://www.mrbrklyn.com
DRM is THEFT - We are the STAKEHOLDERS - RI Safir 2002
http://www.nylxs.com - Leadership Development in Free Software
http://www2.mrbrklyn.com/resources - Unpublished Archive
http://www.coinhangout.com - coins!
http://www.brooklyn-living.com
Being so tracked is for FARM ANIMALS and and extermination camps,
but incompatible with living as a free human being. -RI Safir 2013
_______________________________________________
Learn mailing list
Learn-at-nylxs.com
http://lists.mrbrklyn.com/mailman/listinfo/learn
|
|
