MESSAGE
| DATE | 2016-11-09 |
| FROM | Ruben Safir
|
| SUBJECT | Subject: [Learn] merge sort parallel hw
|
From learn-bounces-at-nylxs.com Wed Nov 9 15:52:17 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 C174A161312;
Wed, 9 Nov 2016 15:52:16 -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 255E1160E77;
Wed, 9 Nov 2016 15:52:14 -0500 (EST)
To: learn-at-nylxs.com, Samir Iabbassen
From: Ruben Safir
Message-ID: <6714100a-3ebd-8129-b8bc-6d1db3ae59be-at-mrbrklyn.com>
Date: Wed, 9 Nov 2016 15:52:14 -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="------------EA1C5475F965B901549E987B"
Subject: [Learn] merge sort parallel hw
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.
--------------EA1C5475F965B901549E987B
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit
I can't finish by tonight. I borrowed a mergesort algorithm from the
net at here
http://www.cprogramming.com/tutorial/computersciencetheory/merge.html
I ported it to C++ and it failed to work. I changed the name of the
vars to more sensible names, and converged some of his math because what
was there just seemed to sloppy. I mocked it and merged the last
subroutine directly in main and it just failed to work. So I then
copied and pasted his work and altered it to make it a complete c
program and it does work :(
I can't find what I did wrong. I might have just been better off
writing it by myself but I wanted to finish before class tonight, and to
focus on the thread library.
Its 4PM and I'm out of time. Attached at the cpp files and the c files
They are all part of the C++ code accept for the one with the c sufix.
That one is the copy and paste version. This will take another day at
least.
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
--------------EA1C5475F965B901549E987B
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 20
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;
for(int i = 0; i < SIZE; i++){
cout << "Before: " << i << " ==> " << data[i] << "\t" << endl;
}
merge::track(data, 0, SIZE, cache);
for(int i = 0; i < SIZE; i++){
cout << "After: " << i << "==> " << data[i] << "\t" << endl;
}
return 0;
}
--------------EA1C5475F965B901549E987B
Content-Type: text/plain; charset=UTF-8;
name="makefile"
Content-Transfer-Encoding: base64
Content-Disposition: attachment;
filename="makefile"
Q1hYOj1nKysgCkNYWEZMQUdTOj0tV2FsbCAtZ2dkYiAKCkxERkxBR1M6PS1ML3Vzci9sb2Nh
bC9saWIvbXlzcWwgLWxteXNxbHBwIC1sbXlzcWxjbGllbnQKCm1zb3J0IDoJbXNvcnQubyBt
YWluLm8KCSR7Q1hYfSAgJHtDWFhGTEFHU30gLW8gbXNvcnQgbXNvcnQubyBtYWluLm8KCm1h
aW4ubyA6CW1haW4uY3BwCgkke0NYWH0gICR7Q1hYRkxBR1N9IC1vIG1haW4ubyAtYyBtYWlu
LmNwcAkKCm1zb3J0Lm8gOgltc29ydC5jcHAJbXNvcnQuaAoJJHtDWFh9ICAke0NYWEZMQUdT
fSAtYyBtc29ydC5jcHAKCmNsZWFuCTogCglybSBub2RlcyAqLm8gbWFrZS5kZXBzCgl0b3Vj
aCAqLmNwcCAqLmgKCmluY2x1ZGUgbWFrZS5kZXBzCm1ha2UuZGVwczogKi5jcHAgOyBnY2Mg
LU0gKi5jcHAgPiRACg==
--------------EA1C5475F965B901549E987B
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 max(int x, int y){
int ret;
x>y ? ret=x : ret=y;
std::cout << x << ":" << y << "==>" << ret << std::endl;
return ret;
}
void track(int* in, int left, int right, int* space)
{
int i = 0;
if(right == left + 1){
std::cout << "BACKUP" << std::endl;
return;
}
int length = right - left;
std::cout << "length =>" << length << std::endl;
int mpt = length/2;
std::cout << "mpt =>" << mpt << std::endl;
int pos1 = left;
int pos2 = left + mpt;
int pos3 = right;
std::cout << "pos1 =>" << pos1 << " pos2==>" << pos2 << " pos3==>" << pos3 << std::endl;
//do the recursion now on the left and right branches
std::cout << "LEFT <<==" << std::endl;
track(in, pos1, pos2, space);
std::cout << "RIGHT ==>>" << std::endl;
track(in, pos2, pos3, space);
for(i = 0; i < length; i++)
{
if(pos1 < pos2 && ( pos2 == pos3 || max(in[pos1], in[pos2]) == in[pos1]))
{
space[i] = in[pos1];
pos1++;
}
else{
space[i] = in[pos2];
pos2++;
}
}
/* transfer array segment */
for(i = left; i < right; i++)
{
in[i] = space[i - left];
}
}
}//end namespace
--------------EA1C5475F965B901549E987B
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 max(int x, int y);
void track(int* , int , int , int* );
//int sort(int &input , int size);
}
#endif /* ----- #ifndef MSORT_INC ----- */
--------------EA1C5475F965B901549E987B
Content-Type: text/plain; charset=UTF-8;
name="tmp"
Content-Transfer-Encoding: base64
Content-Disposition: attachment;
filename="tmp"
MTE5CTQ4MAk5MTQJNjI5CTM1MgkxMTEJOTIzCTkyCTYzNgkxNTIJMjg2CTEwNAkyNDQJNDMy
CTYxNwk2NjkJMzY3CTMwOQkxNzQJNDc0CQpfX19fX19fX19fX19fX19fX19fX19fX19fX19f
X19fX19fX19fX19fX19fX19fX19fX19fX19fXwpCZWZvcmU6ICAwID09PiAxMTkJCkJlZm9y
ZTogIDEgPT0+IDQ4MAkKQmVmb3JlOiAgMiA9PT4gOTE0CQpCZWZvcmU6ICAzID09PiA2MjkJ
CkJlZm9yZTogIDQgPT0+IDM1MgkKQmVmb3JlOiAgNSA9PT4gMTExCQpCZWZvcmU6ICA2ID09
PiA5MjMJCkJlZm9yZTogIDcgPT0+IDkyCQpCZWZvcmU6ICA4ID09PiA2MzYJCkJlZm9yZTog
IDkgPT0+IDE1MgkKQmVmb3JlOiAgMTAgPT0+IDI4NgkKQmVmb3JlOiAgMTEgPT0+IDEwNAkK
QmVmb3JlOiAgMTIgPT0+IDI0NAkKQmVmb3JlOiAgMTMgPT0+IDQzMgkKQmVmb3JlOiAgMTQg
PT0+IDYxNwkKQmVmb3JlOiAgMTUgPT0+IDY2OQkKQmVmb3JlOiAgMTYgPT0+IDM2NwkKQmVm
b3JlOiAgMTcgPT0+IDMwOQkKQmVmb3JlOiAgMTggPT0+IDE3NAkKQmVmb3JlOiAgMTkgPT0+
IDQ3NAkKbGVuZ3RoID0+MjAKbXB0ID0+MTAKcG9zMSA9PjAgcG9zMj09PjEwIHBvczM9PT4y
MApMRUZUIDw8PT0KbGVuZ3RoID0+MTAKbXB0ID0+NQpwb3MxID0+MCBwb3MyPT0+NSBwb3Mz
PT0+MTAKTEVGVCA8PD09Cmxlbmd0aCA9PjUKbXB0ID0+Mgpwb3MxID0+MCBwb3MyPT0+MiBw
b3MzPT0+NQpMRUZUIDw8PT0KbGVuZ3RoID0+MgptcHQgPT4xCnBvczEgPT4wIHBvczI9PT4x
IHBvczM9PT4yCkxFRlQgPDw9PQpCQUNLVVAKUklHSFQgPT0+PgpCQUNLVVAKMTE5OjQ4MD09
PjQ4MApSSUdIVCA9PT4+Cmxlbmd0aCA9PjMKbXB0ID0+MQpwb3MxID0+MiBwb3MyPT0+MyBw
b3MzPT0+NQpMRUZUIDw8PT0KQkFDS1VQClJJR0hUID09Pj4KbGVuZ3RoID0+MgptcHQgPT4x
CnBvczEgPT4zIHBvczI9PT40IHBvczM9PT41CkxFRlQgPDw9PQpCQUNLVVAKUklHSFQgPT0+
PgpCQUNLVVAKNjI5OjM1Mj09PjYyOQo5MTQ6NjI5PT0+OTE0CjYyOTozNTI9PT42MjkKNDgw
OjkxND09PjkxNAo0ODA6NjI5PT0+NjI5CjQ4MDo2Mjk9PT42MjkKUklHSFQgPT0+PgpsZW5n
dGggPT41Cm1wdCA9PjIKcG9zMSA9PjUgcG9zMj09PjcgcG9zMz09PjEwCkxFRlQgPDw9PQps
ZW5ndGggPT4yCm1wdCA9PjEKcG9zMSA9PjUgcG9zMj09PjYgcG9zMz09PjcKTEVGVCA8PD09
CkJBQ0tVUApSSUdIVCA9PT4+CkJBQ0tVUAoxMTE6OTIzPT0+OTIzClJJR0hUID09Pj4KbGVu
Z3RoID0+MwptcHQgPT4xCnBvczEgPT43IHBvczI9PT44IHBvczM9PT4xMApMRUZUIDw8PT0K
QkFDS1VQClJJR0hUID09Pj4KbGVuZ3RoID0+MgptcHQgPT4xCnBvczEgPT44IHBvczI9PT45
IHBvczM9PT4xMApMRUZUIDw8PT0KQkFDS1VQClJJR0hUID09Pj4KQkFDS1VQCjYzNjoxNTI9
PT42MzYKOTI6NjM2PT0+NjM2CjkyOjE1Mj09PjE1Mgo5MjM6NjM2PT0+OTIzCjExMTo2MzY9
PT42MzYKMTExOjE1Mj09PjE1MgoxMTE6OTI9PT4xMTEKNjM2OjkyPT0+NjM2CjkxNDo5MjM9
PT45MjMKOTE0OjYzNj09PjkxNAo2Mjk6NjM2PT0+NjM2CjYyOToxNTI9PT42MjkKNjI5OjE1
Mj09PjYyOQo0ODA6MTUyPT0+NDgwCjExOToxNTI9PT4xNTIKMTE5OjExMT09PjExOQo5MjM6
MTExPT0+OTIzCjYzNjoxMTE9PT42MzYKUklHSFQgPT0+PgpsZW5ndGggPT4xMAptcHQgPT41
CnBvczEgPT4xMCBwb3MyPT0+MTUgcG9zMz09PjIwCkxFRlQgPDw9PQpsZW5ndGggPT41Cm1w
dCA9PjIKcG9zMSA9PjEwIHBvczI9PT4xMiBwb3MzPT0+MTUKTEVGVCA8PD09Cmxlbmd0aCA9
PjIKbXB0ID0+MQpwb3MxID0+MTAgcG9zMj09PjExIHBvczM9PT4xMgpMRUZUIDw8PT0KQkFD
S1VQClJJR0hUID09Pj4KQkFDS1VQCjI4NjoxMDQ9PT4yODYKUklHSFQgPT0+PgpsZW5ndGgg
PT4zCm1wdCA9PjEKcG9zMSA9PjEyIHBvczI9PT4xMyBwb3MzPT0+MTUKTEVGVCA8PD09CkJB
Q0tVUApSSUdIVCA9PT4+Cmxlbmd0aCA9PjIKbXB0ID0+MQpwb3MxID0+MTMgcG9zMj09PjE0
IHBvczM9PT4xNQpMRUZUIDw8PT0KQkFDS1VQClJJR0hUID09Pj4KQkFDS1VQCjQzMjo2MTc9
PT42MTcKMjQ0OjYxNz09PjYxNwoyNDQ6NDMyPT0+NDMyCjI4Njo2MTc9PT42MTcKMjg2OjQz
Mj09PjQzMgoyODY6MjQ0PT0+Mjg2CjEwNDoyNDQ9PT4yNDQKUklHSFQgPT0+PgpsZW5ndGgg
PT41Cm1wdCA9PjIKcG9zMSA9PjE1IHBvczI9PT4xNyBwb3MzPT0+MjAKTEVGVCA8PD09Cmxl
bmd0aCA9PjIKbXB0ID0+MQpwb3MxID0+MTUgcG9zMj09PjE2IHBvczM9PT4xNwpMRUZUIDw8
PT0KQkFDS1VQClJJR0hUID09Pj4KQkFDS1VQCjY2OTozNjc9PT42NjkKUklHSFQgPT0+Pgps
ZW5ndGggPT4zCm1wdCA9PjEKcG9zMSA9PjE3IHBvczI9PT4xOCBwb3MzPT0+MjAKTEVGVCA8
PD09CkJBQ0tVUApSSUdIVCA9PT4+Cmxlbmd0aCA9PjIKbXB0ID0+MQpwb3MxID0+MTggcG9z
Mj09PjE5IHBvczM9PT4yMApMRUZUIDw8PT0KQkFDS1VQClJJR0hUID09Pj4KQkFDS1VQCjE3
NDo0NzQ9PT40NzQKMzA5OjQ3ND09PjQ3NAozMDk6MTc0PT0+MzA5CjQ3NDoxNzQ9PT40NzQK
NjY5OjQ3ND09PjY2OQozNjc6NDc0PT0+NDc0CjM2NzozMDk9PT4zNjcKNDc0OjMwOT09PjQ3
NAo2MTc6NjY5PT0+NjY5CjYxNzo0NzQ9PT42MTcKNDMyOjQ3ND09PjQ3NAo0MzI6MzY3PT0+
NDMyCjI4NjozNjc9PT4zNjcKMjg2OjQ3ND09PjQ3NAoyODY6MzA5PT0+MzA5CjkyMzo2Njk9
PT45MjMKOTE0OjY2OT09PjkxNAo2MzY6NjY5PT0+NjY5CjYzNjo2MTc9PT42MzYKNjI5OjYx
Nz09PjYyOQo2Mjk6NjE3PT0+NjI5CjQ4MDo2MTc9PT42MTcKNDgwOjQ3ND09PjQ4MAoxNTI6
NDc0PT0+NDc0CjE1Mjo0MzI9PT40MzIKMTUyOjM2Nz09PjM2NwoxNTI6NDc0PT0+NDc0CjE1
MjozMDk9PT4zMDkKMTUyOjI4Nj09PjI4NgoxNTI6MjQ0PT0+MjQ0CjE1MjoxMDQ9PT4xNTIK
MTE5OjEwND09PjExOQo5MjM6MTA0PT0+OTIzCjYzNjoxMDQ9PT42MzYKNjY5OjEwND09PjY2
OQpBZnRlcjogMD09PiA5MjMJCkFmdGVyOiAxPT0+IDkxNAkKQWZ0ZXI6IDI9PT4gNjY5CQpB
ZnRlcjogMz09PiA2MzYJCkFmdGVyOiA0PT0+IDYyOQkKQWZ0ZXI6IDU9PT4gNjI5CQpBZnRl
cjogNj09PiA2MTcJCkFmdGVyOiA3PT0+IDQ4MAkKQWZ0ZXI6IDg9PT4gNDc0CQpBZnRlcjog
OT09PiA0MzIJCkFmdGVyOiAxMD09PiAzNjcJCkFmdGVyOiAxMT09PiA0NzQJCkFmdGVyOiAx
Mj09PiAzMDkJCkFmdGVyOiAxMz09PiAyODYJCkFmdGVyOiAxND09PiAyNDQJCkFmdGVyOiAx
NT09PiAxNTIJCkFmdGVyOiAxNj09PiAxMTkJCkFmdGVyOiAxNz09PiA5MjMJCkFmdGVyOiAx
OD09PiA2MzYJCkFmdGVyOiAxOT09PiA2NjkJCg==
--------------EA1C5475F965B901549E987B
Content-Type: text/x-csrc;
name="merge.c"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="merge.c"
#include "stdlib.h"
#include "time.h"
#include "stdio.h"
#define SIZE 500
/* Helper function for finding the max of two numbers */
int max(int x, int y)
{
if(x > y)
{
return x;
}
else
{
return y;
}
}
/* left is the index of the leftmost element of the subarray; right is one
* past the index of the rightmost element */
void merge_helper(int *input, int left, int right, int *scratch)
{
/* base case: one element */
if(right == left + 1)
{
return;
}
else
{
int i = 0;
int length = right - left;
int midpoint_distance = length/2;
/* l and r are to the positions in the left and right subarrays */
int l = left, r = left + midpoint_distance;
/* sort each subarray */
merge_helper(input, left, left + midpoint_distance, scratch);
merge_helper(input, left + midpoint_distance, right, scratch);
/* merge the arrays together using scratch for temporary storage */
for(i = 0; i < length; i++)
{
/* Check to see if any elements remain in the left array; if so,
* we check if there are any elements left in the right array; if
* so, we compare them. Otherwise, we know that the merge must
* use take the element from the left array */
if(l < left + midpoint_distance &&
(r == right || max(input[l], input[r]) == input[l]))
{
scratch[i] = input[l];
l++;
}
else
{
scratch[i] = input[r];
r++;
}
}
/* Copy the sorted subarray back to the input */
for(i = left; i < right; i++)
{
input[i] = scratch[i - left];
}
}
}
/* mergesort returns true on success. Note that in C++, you could also
* replace malloc with new and if memory allocation fails, an exception will
* be thrown. If we don't allocate a scratch array here, what happens?
*
* Elements are sorted in reverse order -- greatest to least */
int mergesort(int *input, int size)
{
int *scratch = (int *)malloc(size * sizeof(int));
if(scratch != NULL)
{
merge_helper(input, 0, size, scratch);
free(scratch);
return 1;
}
else
{
return 0;
}
}
int main(int argc, char** argv)
{
int *data = (int *)malloc(SIZE * sizeof(int ));
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;
printf("%i \t", data[i] );
}
printf("\n");
printf ("________________________________________________________\n");
mergesort(data, SIZE);
for(int i = 0; i < SIZE; i++){
printf("%i \t", data[i] );
}
printf("\n");
return 0;
}
--------------EA1C5475F965B901549E987B
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
--------------EA1C5475F965B901549E987B--
|
|
