brute_force_approach.py 6 KB
Newer Older
Long Chung Chan's avatar
Long Chung Chan committed
1 2 3
import sys
import time
import csv
LongChan's avatar
LongChan committed
4
import path_constant as pc
Long Chung Chan's avatar
Long Chung Chan committed
5 6 7 8 9 10 11 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

from tqdm import tqdm
from itertools import combinations


class brute_force(object):
    def __init__(self, 
        # data path
        path_to_datasrc = "googlenet_mem_bound.csv",
        path_to_topology = "googlenet.csv",
        target_col = "DRAM_cycle",
        
        # problem definition
        number_of_partition = 4,

        # constraint
        max_res_available = 960, initial_res = 0, 
        res_step = 1,
        ):

        self.topology_file = path_to_topology

        self.k = number_of_partition
        self.best_candidate = [0] * number_of_partition

        self.max_res_unit = max_res_available
        self.res_step = res_step

        self.target_col = target_col
        self.data_src = {}
        self.layers = self.parse_topology_file()
        self.parse_data_set_file(path_to_datasrc)
        self.ending_iter = 0

        self.start = time.time()

    def parse_topology_file(self):
        layers = []
LongChan's avatar
LongChan committed
43
        with open(pc.TOPOLOGIES_PATH+self.topology_file, 'r') as f:
Long Chung Chan's avatar
Long Chung Chan committed
44 45 46 47 48 49 50 51 52 53 54 55
            next(f)
            for line in f:
                elems = line.strip().split(',')
                layers.append(elems[0])

        for layer in layers:
            self.data_src[layer] = {}
        return layers
    
    def parse_data_set_file(self, path_to_data_csv):
        first = True
        target_idx = 2
LongChan's avatar
LongChan committed
56
        with open(pc.DATA_SOURCE_PATH+path_to_data_csv, 'r') as f:
Long Chung Chan's avatar
Long Chung Chan committed
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 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153
            for line in f:
                elems = line.strip().split(',')
                # #print(elems)
                if first:
                    for idx, col in enumerate(elems):
                        if self.target_col in col:
                            target_idx = idx
                            break
                    first = False
                else:
                    self.data_src[elems[1]][int(elems[0])] = int(float(elems[target_idx]))

    def decode_gene(self, gene):
        gene = list(gene)
        solution_layer_domain = []
        part = []
        idx = 0

        for idx, l in enumerate(self.layers):
            if not gene:
                part = self.layers[idx:]
                solution_layer_domain.append(part)
                break
            
            part.append(l)
            if idx == gene[0]:
                solution_layer_domain.append(part)
                part = []
                gene.pop(0)

        return solution_layer_domain

    def generate_gene(self):
        return list(combinations(list(range(len(self.layers) - 1)), self.k-1))
        # for g in genes:
        #     print(g, self.decode_gene(g))
        # print("sizes:", len(genes))

    def find_max_latency(self, layer_partition, res_partitions):
        latencies = [0] * len(layer_partition)
        max_latency_idx = 0

        for idx, part in enumerate(layer_partition):
            res = res_partitions[idx]
            for layer in part:
                latencies[idx] += self.data_src[layer][res]
            if latencies[idx] > latencies[max_latency_idx]:
                max_latency_idx = idx

        return latencies, max_latency_idx

    def evaluate_hybird(self, gene):
        layer = self.decode_gene(gene)
        res = [self.res_step] * self.k
        latencies = []

        for _ in range(0, int(self.max_res_unit/self.res_step - self.k*self.res_step)):
            latencies, max_idx = self.find_max_latency(layer, res)
            res[max_idx] += self.res_step

        return latencies[max_idx], latencies, res, layer, gene     

    def run(self):
        min_latency = 100000000
        for g in tqdm(self.generate_gene()):
            lat, _, _, _, _ = self.evaluate_hybird(g)
            if lat < min_latency:
                self.best_candidate = g
                min_latency = lat

        self.end = time.time()

    def report(self):
        max_latency = 0
        layer = []
        res = []
        latencies = []
        full_latency, full_max_idx = self.find_max_latency([self.layers], [self.max_res_unit]*len(self.layers))
        max_latency = 100000000

        max_latency, latencies, res, layer, _ = self.evaluate_hybird(self.best_candidate)
        
        print("================================= RESULT =================================")
        print("Layer assignment:")
        print(layer)
        print("Res mapping:")
        print(res)
        print("Latency for each partition: ")
        print(latencies)
        print("Final Latency:", max_latency*self.k, "|| Throught put:", 1/max_latency)
        print("==========================================================================")
        print("Map to full array (", self.max_res_unit, ")")
        print("Final Latency:", full_latency[full_max_idx], "|| Throught put:", 1/full_latency[full_max_idx])
        print("==========================================================================")
        print("Throughtput Ratio:", (1/max_latency)/(1/full_latency[full_max_idx]))
        print("Latency increase:", (max_latency*self.k)/full_latency[full_max_idx])

LongChan's avatar
LongChan committed
154
        with open(pc.RESULT_CSV_PATH+'bruteforce.csv', 'a') as csvFile:
Long Chung Chan's avatar
Long Chung Chan committed
155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175
            writer = csv.writer(csvFile, delimiter=',', lineterminator="\n")
            writer.writerow([self.target_col,self.k, self.topology_file, 1,(1/max_latency), max_latency*self.k, 1/full_latency[full_max_idx], full_latency[full_max_idx], (1/max_latency)/(1/full_latency[full_max_idx]), (max_latency*self.k)/full_latency[full_max_idx], layer, res, self.end-self.start, self.max_res_unit])
        csvFile.close

if __name__ == "__main__":

    print("Brute Force")
    # python3 brute_force_approach.py googlenet 20 960 DRAM_cycle
    topology = sys.argv[1]
    k = int(sys.argv[2])
    max_res_unit = int(sys.argv[3])
    target_col = sys.argv[4]

    bf = brute_force(
        path_to_datasrc = str(topology)+"_mem_bound.csv",
        path_to_topology = str(topology)+".csv",
        target_col = str(target_col),

        number_of_partition = k,

        max_res_available = max_res_unit, initial_res = 0, 
LongChan's avatar
LongChan committed
176
        res_step = 1
Long Chung Chan's avatar
Long Chung Chan committed
177 178 179 180 181
    )

    # bf.generate_gene()
    bf.run()
    bf.report()