MESSAGE
| DATE | 2016-11-12 |
| FROM | Ruben Safir
|
| SUBJECT | Subject: [Learn] HW of mergesort in parallel
|
From learn-bounces-at-nylxs.com Sat Nov 12 18:59:29 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 CAADA161312;
Sat, 12 Nov 2016 18:59:28 -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 96067160E77
for ; Sat, 12 Nov 2016 18:59:24 -0500 (EST)
To: learn-at-nylxs.com
From: Ruben Safir
Message-ID:
Date: Sat, 12 Nov 2016 18:59:24 -0500
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101
Thunderbird/45.4.0
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="------------A0BD793C493578214428EC26"
Subject: [Learn] HW of mergesort in parallel
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: ,
Errors-To: learn-bounces-at-nylxs.com
Sender: "Learn"
This is a multi-part message in MIME format.
--------------A0BD793C493578214428EC26
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit
I've look at things and decided that I need to understand mergesort
better to do this. So I looked at a couple texts on the algorithm and
thought that none of the coding examples really make it mechanisms
understandable, so I decided to give it my own shot.
My resulting code needs to be paralyzed for the HW assignment (which is
now very late I might add). So this is my effort. At least, I hope, I
will know where I am in the sorting process.
I have to say this was not easy for me. I should have been better at
this. Until I finally put aside the idea of cutting and pasting someone
elses work, I really didn't comprehend the details of this.
One of the major issues was that it is possible, even likely, that there
would be a tail on the initial sorting mechanism. It is build on the
sclaffing of a binary tree. In fact, I build the tree first with a
slew of recursive functions, that than loops. Then I added the data and
the sort. Having functions allows me easier access to threading.
Now I have a few considerations. First, I have two kinds of behaviors
for possible threads. Parent processes merge child results. So that
means I can thread and parallelize sibling nodes on the same level, but
threads created by parent which produce children, they need to wait for
all the children to return and then merge.
I also looked at the thread slice. Not as closely as I will, but I'll
get to it. This and a number of C++ syntax changes might make this code
much cleaner. I'll have to see later. I have limited time available to
explore this and I type sooo slow.
Ruben
--
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
--------------A0BD793C493578214428EC26
Content-Type: text/x-chdr;
name="msort.h"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="msort.h"
/*
* =====================================================================================
*
* 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 ----- */
--------------A0BD793C493578214428EC26
Content-Type: text/x-c++src;
name="msort.cpp"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="msort.cpp"
#include "msort.h"
#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;
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;
track(m, k, parent);
std::cout << "Returned to Node j => " << j << "\tk=> " << k << " From the right" << std::endl;
std::cout << "**********MERGE**********" << std::endl;
merge(j,l,m,k, parent);
}
}//end namespace
--------------A0BD793C493578214428EC26
Content-Type: text/x-c++src;
name="main.cpp"
Content-Transfer-Encoding: 8bit
Content-Disposition: attachment;
filename="main.cpp"
/*
* =====================================================================================
*
* Filename: main.cpp
*
* Description: merge sort main
*
* Version: 1.0
* Created: 11/09/2016 09:33:20 AM
* Revision: none
* Compiler: gcc
*
* Author: Dr. Fritz Mehner (mn), mehner-at-fh-swf.de
* Company: FH Südwestfalen, Iserlohn
*
* =====================================================================================
*/
#include
#include "msort.h"
#include
#include
#define SIZE 2500000
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() % 1000;
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;
}
--------------A0BD793C493578214428EC26
Content-Type: text/plain; charset=UTF-8;
name="makefile"
Content-Transfer-Encoding: base64
Content-Disposition: attachment;
filename="makefile"
Q1hYOj1nKysgCkNYWEZMQUdTOj0tV2FsbCAtZ2dkYiAgLXBnCgpMREZMQUdTOj0tTC91c3Iv
bG9jYWwvbGliL215c3FsIC1sbXlzcWxwcCAtbG15c3FsY2xpZW50Cgptc29ydCA6CW1zb3J0
Lm8gbWFpbi5vCgkke0NYWH0gICR7Q1hYRkxBR1N9IC1vIG1zb3J0IG1zb3J0Lm8gbWFpbi5v
CgptYWluLm8gOgltYWluLmNwcAoJJHtDWFh9ICAke0NYWEZMQUdTfSAtbyBtYWluLm8gLWMg
bWFpbi5jcHAJCgptc29ydC5vIDoJbXNvcnQuY3BwCW1zb3J0LmgKCSR7Q1hYfSAgJHtDWFhG
TEFHU30gLWMgbXNvcnQuY3BwCgpjbGVhbgk6IAoJcm0gbm9kZXMgKi5vIG1ha2UuZGVwcwoJ
dG91Y2ggKi5jcHAgKi5oCgppbmNsdWRlIG1ha2UuZGVwcwptYWtlLmRlcHM6ICouY3BwIDsg
Z2NjIC1NICouY3BwID4kQAo=
--------------A0BD793C493578214428EC26
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
_______________________________________________
Learn mailing list
Learn-at-nylxs.com
http://lists.mrbrklyn.com/mailman/listinfo/learn
--------------A0BD793C493578214428EC26--
|
|
