The unified diff between revisions [8ad2cbb1..] and [df65b9ec..] is displayed below. It can also be downloaded as a raw diff.
#
#
# patch "aca319/gen-rand.py"
# from [4a6fa6adb0ea87655042628f983f49775800cab5]
# to [9bf287499fdf3bf623b2ddece4f45054d753306e]
#
# patch "aca319/lab7q1.c"
# from [faa415d2e67b7d4e55638298bec634720765dc44]
# to [487d6daabdb75a56cbb61ed9b5bbe7f9afe63bdf]
#
============================================================
--- aca319/gen-rand.py 4a6fa6adb0ea87655042628f983f49775800cab5
+++ aca319/gen-rand.py 9bf287499fdf3bf623b2ddece4f45054d753306e
@@ -4,4 +4,4 @@ if __name__ == '__main__':
if __name__ == '__main__':
for i in range(500):
+ print "%d" % (random.randint(1,500))
- print "%d" % (random.randint(0,500))
============================================================
--- aca319/lab7q1.c faa415d2e67b7d4e55638298bec634720765dc44
+++ aca319/lab7q1.c 487d6daabdb75a56cbb61ed9b5bbe7f9afe63bdf
@@ -1,13 +1,17 @@
#include <stdio.h>
#include <stdlib.h>
+#include <string.h>
#include "mpi.h"
#include "mpe.h"
#define FALSE 0
#define TRUE !(FALSE)
-#define INPUT_VECTOR_SIZE 100
+#define INPUT_VECTOR_SIZE 500
+#define VECTOR_TERMINATOR 0
+#define INPUT_MIN 1
+#define INPUT_MAX 500
int ev_start_compute, ev_end_compute;
@@ -16,7 +20,7 @@ int
* values < 0 are not permitted
*/
int
-read_from_file(const char *filename, int *dataset, int *min, int *max)
+read_from_file(const char *filename, int *dataset)
{
FILE *f = fopen(filename, "r");
int val;
@@ -28,8 +32,6 @@ read_from_file(const char *filename, int
}
while ((i < INPUT_VECTOR_SIZE) && (fscanf(f, "%d\n", &val) != EOF)) {
dataset[i] = val;
- if (val > *max) *max = val;
- if (val < *min) *min = val;
i++;
}
if (i < INPUT_VECTOR_SIZE) {
@@ -40,54 +42,116 @@ void
}
void
-master(int rank, int size)
+print_bucket(int rank, int *bucket)
{
- int input_min, input_max;
- int dataset[INPUT_VECTOR_SIZE];
-
- /* first of all, read our input file */
- if (!read_from_file("lab7in.txt", dataset, &input_min, &input_max)) {
- fprintf(stderr, "Unable to read input file!\n");
- return;
+ int i;
+ printf("node %d: ", rank);
+ for (i=0;i<INPUT_VECTOR_SIZE;i++) {
+ printf("%d ", bucket[i]);
}
- fprintf(stderr, "[%d] dataset has min of %d and max of %d\n", rank, input_min, input_max);
-
- /* check that the dataset splits evenly over size */
- if (INPUT_VECTOR_SIZE % size != 0) {
- fprintf(stderr, "Input vector does not split evenly over this number of processors. Abort.\n");
- }
+ printf("\n");
}
-
-void
-slave(int rank, int size)
+int
+int_compare(const void *a, const void *b)
{
-
-
-
+ int c = *(int *)a;
+ int d = *(int *)b;
+ return d - c;
}
int
main(int argc, char *argv[])
{
- int rank, size;
+ int rank, size, comm_size;
+ int scatter_size;
+ int send_array[INPUT_VECTOR_SIZE];
+ int recv_array[INPUT_VECTOR_SIZE];
+ int *buckets, *recv_buckets;
+ int *bucket_lengths;
+ int i, j, target_bucket;
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI_Comm_size(MPI_COMM_WORLD, &size);
+ MPI_Comm_size(MPI_COMM_WORLD, &comm_size);
MPE_Init_log();
ev_start_compute = MPE_Log_get_event_number();
ev_end_compute = MPE_Log_get_event_number();
+ buckets = malloc(comm_size * INPUT_VECTOR_SIZE * sizeof(int));
+ recv_buckets = malloc(comm_size * INPUT_VECTOR_SIZE * sizeof(int));
+ bucket_lengths = calloc(comm_size, sizeof(int));
+ if (!buckets || !bucket_lengths || !recv_buckets) {
+ fprintf(stderr, "Unable to allocate memory for buckets\n");
+ return -1;
+ }
+ memset(buckets, VECTOR_TERMINATOR, comm_size * INPUT_VECTOR_SIZE * sizeof(int));
+ memset(recv_buckets, VECTOR_TERMINATOR, comm_size * INPUT_VECTOR_SIZE * sizeof(int));
+
+ /* check that the dataset splits evenly over size */
+ if (INPUT_VECTOR_SIZE % comm_size != 0) {
+ fprintf(stderr, "Input vector does not split evenly over this number of processors. Abort.\n");
+ }
+
+ /* first of all, read our input file */
if (rank == 0) {
- master(rank, size);
- } else {
- slave(rank, size);
+ if (!read_from_file("lab7in.txt", send_array)) {
+ fprintf(stderr, "Unable to read input file!\n");
+ return -1;
+ }
}
+ /* initialise receive array */
+ memset(recv_array, VECTOR_TERMINATOR, sizeof(recv_array));
+
+ /* scatter arrays away from node 0 */
+ scatter_size = INPUT_VECTOR_SIZE / comm_size;
+ MPI_Scatter(send_array, scatter_size, MPI_INT, recv_array, scatter_size, MPI_INT, 0, MPI_COMM_WORLD);
+ //printf("I am node %d, and I have as my first receive element: %d\n", rank, recv_array[0]);
+
+ /* now sort our data into the proper bucket */
+ for (i=0;i<scatter_size;i++) {
+ target_bucket = recv_array[i] / ((INPUT_MAX - INPUT_MIN) / comm_size);
+ if (target_bucket >= comm_size)
+ target_bucket = comm_size - 1;
+ buckets[(target_bucket * INPUT_VECTOR_SIZE) + bucket_lengths[target_bucket]] = recv_array[i];
+ bucket_lengths[target_bucket]++;
+ }
+
+ /* now send buckets from all to all */
+ MPI_Alltoall(buckets, INPUT_VECTOR_SIZE, MPI_INT, recv_buckets, INPUT_VECTOR_SIZE, MPI_INT, MPI_COMM_WORLD);
+
+ /* at this point we have in recv_buckets a list of either VECTOR_TERMINATOR or values in our range
+ * call qsort() on it; as our terminator is LESS than other values we'll sort in reverse order and then
+ * output backwards
+ */
+ qsort(recv_buckets, comm_size * INPUT_VECTOR_SIZE, sizeof(int), int_compare);
+
+ /* we need to move the memory on our node to the right spot so that the gather can work */
+ memmove(recv_buckets + (INPUT_VECTOR_SIZE * rank), recv_buckets, sizeof(int) * INPUT_VECTOR_SIZE);
+
+ //for (i=0;i<comm_size;i++) {
+ // print_bucket(rank, buckets + i * INPUT_VECTOR_SIZE);
+ //}
+
+ /* and now the first bucket in recv_buckets will have our section, sorted.. so call MPI_Gather */
+ MPI_Gather(recv_buckets, INPUT_VECTOR_SIZE, MPI_INT, buckets, INPUT_VECTOR_SIZE, MPI_INT, 0, MPI_COMM_WORLD);
+
+ /* and now node 0 has all of the values sorted neatly into its "buckets" variable */
+ if (rank == 0) {
+ for (i=0;i<comm_size;i++) {
+ for (j=0;j<INPUT_VECTOR_SIZE;j++) {
+ int val = buckets[i * INPUT_VECTOR_SIZE + (INPUT_VECTOR_SIZE - j - 1)];
+ if (val != VECTOR_TERMINATOR)
+ printf("%d\n", val);
+ }
+ }
+ }
+
MPE_Finish_log("lab7q1");
MPI_Finalize();