Newer
Older
/***********************************************************************************************
*cr University of Patras, Greece
*cr Copyright (c) 2015 University of Patras
*cr All rights reserved
*cr
*cr Developed by: HPClab
*cr Computer Engineering and Informatics Department
*cr University of Patras
*cr
***********************************************************************************************/
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <omp.h>
#include <math.h>
#include <float.h>
#include <stdio.h>
#include <alloca.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>
#include <sys/time.h>
/*
* Each line of the input data file must be less than this value.
*/
#define BUFFER_SIZE (1024*1024)
/*
* Define the alignment in bytes that is required for optimal vectorization
*/
#define ALIGNMENT 64
#define TWO_MEANS_TOLERANCE 1.0e-4
#define TWO_MEANS_MAX_ITERATIONS 50
#define POWER_ITERATION_TOLERANCE 1.0e-8
#define POWER_ITERATION_MAX_ITERATIONS 5000
//#define DEBUG 1
#if defined(DEBUG)
#define DBG(format, ...) printf(format, __VA_ARGS__)
#else
#define DBG(format, ...)
#endif
struct node {
unsigned long *indices; /* Number of data_points in the cluster (data_points) */
double *centroid; /* The mean vector for the cluster (attributes) */
struct node *leftchild;
struct node *rightchild;
struct node *sibling;
double scat; /* Total scatter value for the cluster */
unsigned long num_of_indices; /* Number of elements in vector 'indices' */
unsigned long keep_in_tree;
unsigned long is_splittable;
};
typedef struct node Node;
/*******************************************************************************/
#pragma offload_attribute (push,target(mic))
void print_elapsed_time(struct timeval start, struct timeval end, char *msg);
Node *allocate_node(unsigned long data_points);
void init_node(Node *node, Node *sibling, double *M, unsigned long data_points, unsigned long *indices, double *centroid, unsigned long attributes, unsigned long padded_attributes, unsigned long threads);
void process_node(Node *node, double *M, unsigned long attributes, unsigned long padded_attributes, unsigned long current_level, unsigned long max_level);
double calc_scatter(Node *node, double *M, unsigned long attributes, unsigned long padded_attributes, unsigned long threads);
void vector_2_means(Node *node, double *M, double *v, unsigned long attributes, unsigned long padded_attributes, unsigned long **l_indices, unsigned long **r_indices, double **l_centroid, double **r_centroid, unsigned long *l_data_points, unsigned long *r_data_points, unsigned long threads);
void power_iteration(Node *node, double *M, unsigned long attributes, unsigned long padded_attributes, double **v, unsigned long threads);
void reset_nodes_to_keep(Node *node);
void keep_all_nodes(Node *node);
void find_max_scatter_value(Node *node, Node **K);
unsigned long find_nodes_to_keep(Node *node, unsigned long clusters);
double max_cluster_diameter(Node *node, double *M, unsigned long attributes, unsigned long padded_attributes);
void find_all_leaves(Node *node, Node **cluster_nodes, unsigned long *cluster_num);
void find_all_splittable_leaves(Node *node, Node **cluster_nodes, unsigned long *cluster_num);
double min_cluster_distance(Node *node, unsigned long clusters, unsigned long attributes);
void post_order_traversal(Node *node, unsigned long *indices, unsigned long *cluster);
void assign_cluster_numbers(Node *node, unsigned long *result, unsigned long data_points);
#pragma offload_attribute (pop)
void write_results(unsigned long *result, unsigned long data_points, char *filename);
/*******************************************************************************/