Skip to content
Snippets Groups Projects
ilp_scheduler.py 8.37 KiB
Newer Older
Sergii Vystoropskyi's avatar
Sergii Vystoropskyi committed
import random
import pprint
import sys

# Each insn is a python dictionary (map) with the following fields:
# 
#   src1 - operand #1 source register id
#   src2 - operand #2 source register id
#   dst - destination register id
# 
# Register id's are just integers.  There are 16 architectural
# registers in this simple ISA, with id's 0 to 15.
# 
# There are two additional fields which you should fill in as you
# schedule instructions according to their dependences.
#
#   consumer_insns - list of insns that consume output of this insn
#   depth - depth of insn in the scheduling tree

def gen_insns(n):
    # Unique root insn to make sure our dependencies form a tree.
    insns = [ {'src1':0, 'src2':0, 'dst':0,
               'consumer_insns':[], 'depth':0} ]

    live_regs = set([0]) # start out with only 1 live reg
    for i in range(n):
        insn = {}
        insn['src1'] = random.choice(list(live_regs))
        insn['src2'] = random.choice(list(live_regs))
        insn['dst'] = random.randint(0, 15)
        live_regs.add(insn['dst'])

        # Used for building dependence tree.
        insn['consumer_insns'] = []

        # Used for calculating program latency.
        insn['depth'] = None

        insns.append(insn)
    return insns


instr_map = {0:0}
write_instr_counter = 0

def rename(insn):
    global write_instr_counter
    insn['osrc1'] = insn['src1']
    insn['osrc2'] = insn['src2']
    insn['odst'] = insn['dst']

    if insn['src1'] not in instr_map:
        instr_map[insn['src1']] = write_instr_counter
        write_instr_counter += 1
    insn['src1'] = instr_map[insn['src1']]

    if insn['src2'] not in instr_map:
        instr_map[insn['src2']] = write_instr_counter
        write_instr_counter += 1
    insn['src2'] = instr_map[insn['src2']]

    write_instr_counter += 1
    instr_map[insn['dst']] = write_instr_counter
    insn['dst'] = write_instr_counter

def compute_latency(insns):
    def find_producer(insns, r, instr):
        for i in insns:
            if i['dst'] == r:
                if instr not in i['consumer_insns']:
                    i['consumer_insns'].append(instr)
                return i['depth']
        return -1
    lat = 0
    for i in insns:
        if i['depth'] is not None:
            continue

        i['depth'] = max(find_producer(insns, i['src1'], i), find_producer(insns, i['src2'], i))+1
        lat = max(lat, i['depth'])
    return lat + 1

def compute_max_width(insns):
    d = {}
    for i in insns:
        if i['depth'] not in d:
            d[i['depth']] = 1
        else:
            d[i['depth']] += 1

    res = 0

    for k in d:
        res = max(res, d[k])

    return res

def compute_max_pregs(insns):
    def get_instr_by_depth(insns):
        tmp = {}
        res = []
        max_depth = 0
        for i in insns:

            if i['depth'] not in tmp:
                tmp[i['depth']] = [i]
            else:
                tmp[i['depth']].append(i)
                tmp[i['depth']].sort(key=lambda x : x['number'])

            max_depth = max(max_depth, i['depth'])

        for i in range(max_depth+1):
            res.append(tmp[i])

        return res

    def get_commit_order(insns):
        insns = get_instr_by_depth(insns)
        buffer = []
        res = []
        for i in insns:
            buffer = buffer + i
            buffer.sort(key=lambda x:x['number'])
            tmp = [buffer[0]]
            i = 1
            while i < len(buffer) and buffer[i-1]['number']+1 == buffer[i]['number']:
                tmp.append(buffer[i])
                i += 1
            res.append(tmp)
            if i == len(buffer):
                buffer = []
            else:
                buffer = buffer[i:]
        return res

    def get_reg_allocation(insns):
        by_depth = get_instr_by_depth(insns)
        res = []
        for i in range(len(by_depth)):
            if i == 0:
                tmp = set()
            else:
                tmp = set(res[len(res) - 1])
            for ins in by_depth[i]:
                tmp.add(ins['src1'])
                tmp.add(ins['src2'])
                tmp.add(ins['dst'])
            res.append(tmp)
        return res

    def count_reg_usage(insns, reg):
        res = 0
        for ins in insns:
            if reg == ins['src1']:
                res += 1

            if reg == ins['src2']:
                res += 1

            if reg == ins['dst']:
                res += 1

        return res

    def get_reg_free(insns):
        commit_order = get_commit_order(insns)
        not_commited = insns[:]
        commited = []
        res = []
        for i in commit_order:
            s = set()

            if len(res) != 0:
                s = set(res[len(res)-1])

            for ins in i:
                not_commited.remove(ins)
                commited.append(ins)

            for ins in i:
                if count_reg_usage(not_commited, ins['src1']) == 0:
                    s.add(ins['src1'])

                if count_reg_usage(not_commited, ins['src2']) == 0:
                    s.add(ins['src2'])

                if count_reg_usage(not_commited, ins['dst']) == 0:
                    s.add(ins['dst'])
            res.append(s)
        return res

    def get_reg_free2(insns):
        for i,ins in enumerate(insns):
            if ins['odst'] == ins['osrc1']:
                ins['free'] = ins['src1']
                continue
            elif ins['odst'] == ins['osrc2']:
                ins['free'] = ins['src2']
                continue
            elif i > 0:
                for j in reversed(insns[:i]):
                    if j['odst'] == ins['odst']:
                        ins['free'] = j['dst']
                        break
                    elif j['osrc1'] == ins['odst']:
                        ins['free'] = j['src1']
                        break
                    elif j['osrc2'] == ins['odst']:
                        ins['free'] = j['src2']
                        break
        commit_order = get_commit_order(insns)

        res = []
        for instructions  in commit_order:
            tmp = []
            if len(res) != 0:
                tmp = res[len(res) - 1][:]
            for j in instructions:
                if 'free' in j:
                    tmp.append(j['free'])
            res.append(tmp)

        return res

        #return [[i['free'] for i in instctions if 'free' in i] for instctions in commit_order]

    for i,ins in enumerate(insns):
        ins['number'] = i

    reg_free = get_reg_free2(insns)
    reg_alloc = get_reg_allocation(insns)

    mx = len(reg_alloc[0])
    for i in range(1, len(reg_alloc)):
        tmp = len(reg_alloc[i]) - len(reg_free[i-1])
        mx = max(mx,tmp)

    return mx

def main(insns):
    # First, rename insns to remove false dependences.
    for i in insns:
        rename(i)
     
    results = {}

    # Compute latency (versus serial).
    results['latency'] = compute_latency(insns)
    results['serial latency'] = len(insns)

    # Compute max machine width used (max number of insns that
    # executed in parallel).
    results['max machine width used'] = compute_max_width(insns)

    # Compute max number of pregs used.
    results['max pregs used'] = compute_max_pregs(insns)

    return repr(results)

if __name__ == "__main__":
    # Edit this line to run with different trace files (or pass a
    # filename on the command name).
    #filename = "/Users/svystoro/Downloads/hw3-ilp-scheduler/parallel-1tick-6width-7pregs.insns"
    #filename = "/Users/svystoro/Downloads/hw3-ilp-scheduler/serial-6ticks-1width-3pregs.insns"
    #filename = "/Users/svystoro/Downloads/hw3-ilp-scheduler/test-3ticks-1width-4pregs.insns"
    #filename = "/Users/svystoro/Downloads/hw3-ilp-scheduler/test-3ticks-2width-5pregs.insns"
    #filename = "/Users/svystoro/Downloads/hw3-ilp-scheduler/test-4ticks-2width-7pregs.insns"
    #filename = "/Users/svystoro/Downloads/hw3-ilp-scheduler/random-3ticks-3width-4pregs.insns"
    #filename = "/Users/svystoro/Downloads/hw3-ilp-scheduler/random-4ticks-2width-6pregs.insns"
    filename = "/Users/svystoro/Downloads/hw3-ilp-scheduler/random-5ticks-4width-6pregs.insns"

    if len(sys.argv) > 1:
        filename = sys.argv[1]
    pprint.pprint(main( eval(open(filename).read()) ))

    # Uncomment this line to run with a random trace instead.
    # pprint.pprint(main( gen_insns(5) ))

    # This code below will dump a random trace of 5 insns to the
    # terminal, so you can save it as a file and read it back in later.
    # pprint.pprint(gen_insns(5))