Subversion Repositories an-fpga-implementation-of-low-latency-noc-based-mpsoc

/*

Copyright (c) 2014, Mario Badr

All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.

2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

*/

/*

 * TrafficGenerator.cpp

 *

 *  Created on: 2013-01-13

 *      Author: mario

 */

#include <iostream>

#include <list>

#include <math.h>

#include "assert.h"

#include <map>

#include <list>

#include <set>

#include "socketstream.h"

#include "messages.h"

#include "Global.h"

#include "PacketQueue.h"

using namespace std;

//Set this to 0 to debug without connecting to booksim

#define CONNECT 1

SocketStream m_channel;

static unsigned long long next_interval;

static unsigned long long next_hinterval;

static unsigned long long cycle;

static unsigned long int total_pck_queud=0;

int state = 1;

int lastState = 1;

int lastHState = 1;

int messageId = 0;

int allPacketsEjected=0;

//Steady state

map<int, map<int, int> > steadyState;

map<int, int> hSteadyState;

map<int, double> acceptable_mse;

double acceptable_hmse;

struct transaction_t {

    int source;

    int dest;

    int invs_sent;

    int acks_received;

    bool data_received;

    bool unblock_received;

    bool Completed() {

        return (invs_sent == acks_received) && data_received && unblock_received;

    }

    transaction_t() : source(-1), dest(-1), invs_sent(0), acks_received(0),

            data_received(false), unblock_received(false) {}

};

map<int, InjectReqMsg> inTransitPackets;

map<int, transaction_t> inTransitTransactions;

PacketQueue packet_queue;

void TranslateIndex(int index, int& source, int& destination) {

    source = (int) index / 32; //Truncate remainder

    destination = index - (source * 32);

}

void printPacket(InjectReqMsg msg) {

    cout << msg.id << " ";

    cout << cycle << " ";

    cout << msg.source << " ";

    cout << msg.dest << " ";

    cout << msg.packetSize << " ";

    cout << msg.msgType << " ";

    cout << msg.coType << " ";

    cout << msg.address << " ";

    cout << state;

    cout << endl;

}

void connect() {

#if CONNECT

    // connect to network simulator

    assert(m_channel.connect(NS_HOST, NS_PORT) == 0);

    // send request to initialize

    InitializeReqMsg req;

    InitializeResMsg res;

    m_channel << req >> res;

#endif

}

void exit() {

        cout << "Total packet sent to queue: " << total_pck_queud << endl;

#if CONNECT

    // Notify network we are quitting

    QuitReqMsg req;

    QuitResMsg res;

    m_channel << req >> res;

#endif

}

void sendPacket(InjectReqMsg& req) {

    req.id = messageId;

    if((int) req.address == -1) {

        req.address = messageId;

        inTransitTransactions[req.address].source = req.source;

        inTransitTransactions[req.address].dest = req.dest;

        inTransitTransactions[req.address].invs_sent = 0;

        inTransitTransactions[req.address].acks_received = 0;

    }

    messageId++;

    inTransitPackets[req.id] = req;

#if CONNECT

    InjectResMsg res;

    m_channel << req >> res;

#endif

}

double calculate_mse(vector<double> predict, vector<double> actual) {

    if(predict.size() != actual.size()) {

        return -1;

    }

    double sum = 0;

    for(unsigned int i = 0; i < predict.size(); i++) {

        sum += (predict[i] - actual[i]) * (predict[i] - actual[i]);

    }

    return ((double) sum / predict.size());

}

bool InHSteadyState(int numCycles) {

    vector<double> predict;

    int sum = 0;

    for (map<int, int>::iterator it=hSteadyState.begin();

            it!=hSteadyState.end(); ++it) {

        double value =  it->second;

        sum+= value;

        predict.push_back(value);

    }

    for(unsigned int i = 0; i < predict.size(); i++) {

        predict[i] = ((double) predict[i] / sum);

    }

    double mse = calculate_mse(predict, g_hierSState);

    if(mse >= 0 && mse < acceptable_hmse && cycle > numCycles*0.3) {

        return true;

    }

    if(cycle > numCycles*0.7) {

        return true;

    }

    return false;

}

void QueuePacket(int source, int destination, int msgType, int coType,

        int packetSize, int time, int address) {

    InjectReqMsg packet;

    packet.source = source;

    packet.dest = destination;

    packet.cl = 0;

    packet.network = 0;

    packet.packetSize = packetSize;

    packet.msgType = msgType;

    packet.coType = coType;

    packet.address = address;

    packet_queue.Enqueue(packet, time);

    total_pck_queud++;

}

void UniformInject(int writes, int reads, int ccrs, int dcrs) {

    int source, destination;

    UniformDistribution uni_dist(0, g_resolution/2 -1);

    int delta = 0;

    for(int i = 0; i < writes; i++) {

        delta = uni_dist.Generate(0) * 2;

        source = g_writeSpat[g_hierClass][state].Generate(0);

        source = source * 2;

        destination = g_writeDest[g_hierClass][state][source].Generate(0);

        destination = destination * 2 + 1;

        QueuePacket(source, destination, REQUEST, WRITE, CONTROL_SIZE,

                cycle + delta, -1);

    }

    for(int i = 0; i < reads; i++) {

        delta = uni_dist.Generate(0) * 2;

        source = g_readSpat[g_hierClass][state].Generate(0);

        source = source * 2;

        destination = g_readDest[g_hierClass][state][source].Generate(0);

        destination = destination * 2 + 1;

        QueuePacket(source, destination, REQUEST, READ, CONTROL_SIZE,

                cycle + delta, -1);

    }

    for(int i = 0; i < ccrs; i++) {

        delta = uni_dist.Generate(0) * 2;

        source = g_ccrSpat[g_hierClass][state].Generate(0);

        source = source * 2;

        destination = g_ccrDest[g_hierClass][state][source].Generate(0);

        destination = destination * 2 + 1;

        QueuePacket(source, destination, REQUEST, PUTC, CONTROL_SIZE,

                cycle + delta, -1);

    }

    for(int i = 0; i < dcrs; i++) {

        delta = uni_dist.Generate(0) * 2;

        source = g_dcrSpat[g_hierClass][state].Generate(0);

        source = source * 2;

        destination = g_dcrDest[g_hierClass][state][source].Generate(0);

        destination = destination * 2 + 1;

        QueuePacket(source, destination, REQUEST, PUTD, DATA_SIZE,

                cycle + delta, -1);

    }

}

//Volumes

void InitiateMessages() {

    int writes = g_writes[g_hierClass][state].Generate(0);

    int reads = g_reads[g_hierClass][state].Generate(0);

    int ccrs = g_ccrs[g_hierClass][state].Generate(0);

    int dcrs = g_dcrs[g_hierClass][state].Generate(0);

    //cout << "synfull: writes " << writes << " reads " << reads << " ccrs " << ccrs << " dcrs " << dcrs  << endl;

    UniformInject(writes, reads, ccrs, dcrs);

}

void Inject() {

    list<InjectReqMsg> packets = packet_queue.DeQueue(cycle);

    list<InjectReqMsg>::iterator it;

    for(it = packets.begin(); it != packets.end(); ++it) {

        sendPacket(*it);

    }

    packet_queue.CleanUp(cycle);

}

void react(EjectResMsg ePacket) {

    map<int, InjectReqMsg>::iterator it = inTransitPackets.find(ePacket.id);

    if(it == inTransitPackets.end()) {

        cerr << "Error: couldn't find in transit packet " << ePacket.id << endl;

        exit(-1);

    }

    InjectReqMsg request = it->second;

    InjectReqMsg response;

    inTransitPackets.erase(it);

    //cout << "synfull received packet id: " << request.id << " " << cycle  << endl;

    map<int, transaction_t>::iterator trans = inTransitTransactions.find(request.address);

    if(request.msgType == REQUEST &&

            (request.coType == WRITE || request.coType == READ)) {

        //Handle Read/Write Requests

        if((int) request.address == request.id) {

            //This is an initiating request. Should we forward it or go to

            //memory?

            bool isForwarded = g_toForward[g_hierClass][request.dest][request.coType].Generate(0) == 0;

            if(isForwarded) {

                int destination = g_forwardDest[g_hierClass][state][request.dest].Generate(0);

                destination = destination*2;

                if(destination % 2 != 0) {

                    cerr << "Error: Invalid destination for forwarded request." << endl;

                    exit();

                }

                QueuePacket(request.dest, destination, REQUEST, request.coType,

                        CONTROL_SIZE, cycle + 1, request.address);

                if(request.coType == WRITE) {

                    //How many invalidates to send

                    int numInv = g_numInv[g_hierClass][state][request.dest].Generate(0);

                    int s = state;

                    if(numInv <= 0) {

                        return;

                    }

                    //Ensure invalidate destinations are unique (i.e. no two

                    //invalidate messages to the same destination)

                    set<int> destinations;

                    destinations.insert(destination); //Request already forwarded here

                    while(destinations.size() != (unsigned int) numInv) {

                        int dest = g_invDest[g_hierClass][s][request.dest].Generate(0);

                        dest = dest*2;

                        destinations.insert(dest);

                    }

                    for(set<int>::iterator it = destinations.begin();

                            it != destinations.end(); ++it) {

                        QueuePacket(request.dest, *it, REQUEST, INV,

                                CONTROL_SIZE, cycle + 1, request.address);

                        trans->second.invs_sent++;

                    }

                }

            } else {

                //Access memory, queue up a data response for the future

                    //cout << "synfull mem access  id: " << request.id << " src:"<< request.source 

                    //    << " dst:" << request.dest << " addr:" << request.address 

                    //    << " " << cycle  << endl;

                QueuePacket(request.dest, request.source, RESPONSE, DATA,

                        DATA_SIZE, cycle + 80, request.address);

            }

            return;

        } else {

            //This is not an initiating request, so it's a forwarded request

            //if(request.id==52)

            //{

            //    cout << "synfull packet debug  id: " << request.id << " src:"<< request.dest 

            //        << " dst:" << trans->second.source << 

            //           " addr:" << request.address << " " << cycle  << endl;

            //}

            //Respond with Data

            QueuePacket(request.dest,

                    trans->second.source, RESPONSE,

                    DATA, DATA_SIZE, cycle + 1, request.address);

        }

    }

    else if(request.msgType == REQUEST &&

            (request.coType == PUTC || request.coType == PUTD)) {

        //Respond with WB_ACK

        QueuePacket(request.dest, request.source, RESPONSE, WB_ACK,

                CONTROL_SIZE, cycle + 1, request.address);

    }

    else if(request.msgType == REQUEST && request.coType == INV) {

        //Respond with Ack

        QueuePacket(request.dest, trans->second.source,

                RESPONSE, ACK, CONTROL_SIZE, cycle + 1, request.address);

    } else if(request.msgType == RESPONSE && request.coType == DATA) {

        trans->second.data_received = true;

        //Send unblock

        QueuePacket(inTransitTransactions[request.address].source,

                inTransitTransactions[request.address].dest, RESPONSE, UNBLOCK,

                CONTROL_SIZE, cycle + 1, request.address);

    } else if(request.msgType == RESPONSE && request.coType == ACK) {

        trans->second.acks_received++;

    } else if(request.msgType == RESPONSE && request.coType == UNBLOCK) {

                trans->second.unblock_received = true;

        }

    if(trans->second.Completed()) {

        inTransitTransactions.erase(trans);

    }

}

unsigned long long int cntPackets = 0;

void Eject(unsigned int numPackets) {

#if CONNECT

    EjectReqMsg req; //The request to the network

    EjectResMsg res; //The response from the network

    bool hasRequests = true; //Whether there are more requests from the network

    //Loop through all the network's messages

    while(hasRequests) {

        m_channel << req >> res;

        if(res.id >= 0) {

            //Add responses to list

            if(res.id > -1) {

                cntPackets++;

                react(res);

            }

        }

        //Check if there are more messages from the network

        hasRequests = res.remainingRequests;

    }

        if (cntPackets == numPackets)

        {

            allPacketsEjected=1;

        }

#endif

}

void reset_ss() {

    for (std::map<int,int>::iterator it=steadyState[g_hierClass].begin();

            it!=steadyState[g_hierClass].end(); ++it) {

        it->second = 0;

    }

    state = 1;

}

void Run(unsigned int numCycles, bool ssExit, unsigned int numPackets) {

    next_interval = 0;

    next_hinterval = 0;

    //Calculate an acceptable MSE for the Markovian Steady-State

    double sensitivity = 1.04;

    vector<double> predict;

    for (unsigned int i = 0; i < g_hierSState.size(); i++) {

        predict.push_back(((double) g_hierSState[i] * sensitivity));

    }

    acceptable_hmse = calculate_mse(predict, g_hierSState);

    //Connect to network simulator

    connect();

        //Iterate through each cycle and inject packets

        for(cycle = 0; cycle < numCycles; ++cycle) {

            if(cycle >= next_hinterval) {

                next_hinterval += g_timeSpan;

                hSteadyState[g_hierClass]++;

                if(cycle != 0) {

                    lastHState = g_hierClass;

                    g_hierClass = g_hierState[g_hierClass].Generate(0) + 1;

                    reset_ss();

                }

                if(InHSteadyState(numCycles) && ssExit) {

                    cout << "Ending simulation at steady state: " << cycle << endl;

                    break;

                }

                cout << "Current hierarchical state: " << g_hierClass << endl;

            }

            if(cycle >= next_interval) {

                next_interval += g_resolution;

                //Track state history for markovian steady state

                steadyState[g_hierClass][state]++;

                if(cycle != 0) {

                    //Update state

                    lastState = state;

                    state = g_states1[g_hierClass][state].Generate(0) + 1;

                }

                //Queue up initiating messages for injection

                InitiateMessages();

            }

            //Inject all of this cycles' messages into the network

            Inject();

            //Eject from network

            Eject(numPackets);

            if (allPacketsEjected)

            {

                cycle = numCycles;

            }

            //Step the network

#if CONNECT

            StepReqMsg req;

            StepResMsg res;

            m_channel << req >> res;

#endif

        }

    //Close the connection

    exit();

}