Program to find initial collision vector, forbidden and permissible latencies from reservation table

0

Write a Program to find

  1. initial collision vector
  2. forbidden latencies
  3. permissible non-forbidden latencies

from reservation table for pipelined architecture. reservation table will be taken from user as input. (in C,C++, java or python etc)

Answered question
1

program to find forbidden latencies, permissible non-forbidden latencies, initial collision vector from reservation table for pipelined architecture.

#include <iostream>
#include<bits/stdc++.h>
using  namespace std;
void print_reservation_table(int stages,int pulses,int **r_t){
    for(int i=0;i<stages;i++){
        for(int j=0;j<pulses;j++){
            //cout<<"\t"<<*(r_t+(i*pulses+j))<<"\t";
            printf("\t%d\t", *(r_t+(i*pulses+j)));
        }
        cout<<"\n";
    }
}
 int main() {
     int n_stages,n_clock_pulse;
    cout<<"no of stages: ";
    cin>>n_stages;
    cout<<"no of clock pulses: ";
    cin>>n_clock_pulse;
     int reservation_table[n_stages][n_clock_pulse];
    cout<<"enter reservation table in 0/1 format:\n";
    for(int i=0;i<n_stages;i++){
        cout<<"for stage "<<i<<endl;
        for(int j=0;j<n_clock_pulse;j++){
            //cout<<"\t"<<"clock pulse:"<<j<<":";
            cin>>reservation_table[i][j];
        }
        cout<<"\n";
    }
     //collision vector + forbidden latency + permisible latency
    int collision_vector[n_clock_pulse];
    for(int j=0;j<n_clock_pulse;j++)
        collision_vector[j]=0;
     for(int i=0;i<n_stages;i++){
        for(int j=0;j<n_clock_pulse-1;j++){
            if(reservation_table[i][j]>0){//item is marked
                for(int k=j+1;k<n_clock_pulse;k++){
                    if(reservation_table[i][k]>0){
                        collision_vector[k-j]++;//=1;
                    }
                }
            }
        }
    }
    cout<<"forbidden latency [ ";
    for(int j=1;j<n_clock_pulse;j++) {
        if (collision_vector[j]) {
            cout << j << " ";
        }
    }
    cout<<"]\n";
     cout<<"permissible latency [ ";
    for(int j=1;j<n_clock_pulse;j++)
        if(!collision_vector[j])
            cout<<j<<" ";
    cout<<"]\n";
     cout<<"collision vector is c["<<n_clock_pulse-1<<"] to c[1] [ ";
    for(int j=n_clock_pulse-1;j>0;j--) {
        cout << collision_vector[j] << " ";
     }
    cout<<"] \n";
print_reservation_table(n_stages,n_clock_pulse,(int **)reservation_table);
    return 0;
}

Answered question
0

program where the input is a reservation table and output  will be forbidden latency , permissible latency ,ICV, state transition diagram , simple cycle ,greedy cycle and MAL. User will provide the reservation table in the form of a matrix.

#include <bits/stdc++.h>
using namespace std;
map<int,int> visited;
map<string,int> vis;
map<pair<string,int>,vector<pair<string,int>>> adj;
map<string,set<vector<int>>> greedy;
set<vector<int>> ans;
int ICV,big,times;
string icv,highest;
 void recursion(string state,int pos){
    int i,ind,temp,x;
    bool flag = false;
    temp = stoi(state,nullptr,2);
    x=temp;
    if(visited[temp]) {
        return;
    }
    visited[temp]++;
    for(i = state.size()-1;i >= 0; i-- ){
        if(state[i] == '0'){
            flag = true;
            ind = state.size() - i;
            temp = temp>>ind;
            temp = temp | ICV;
            string inter = "";
            while(temp!=0){
                int x;
                x = temp%2;
                inter = to_string(x) + inter;
                temp/=2;
            }
            adj[{state,pos}].push_back(make_pair(inter,ind));
            temp = x;
            recursion(inter,ind);
        }
    }
    if(!flag){
        adj[{state,pos}].push_back(make_pair(icv,times));
    }
    visited[temp]--;
}
 void findCycle(string st,int m,vector<int> &v){
    vis[st]++;
    for(auto it: adj[{st,m}]){
        if(!vis[it.first]){
            v.push_back(it.second);
            findCycle(it.first,it.second,v);
        }
        else if(vis[it.first] and it.second == times){
            v.push_back(it.second);
            ans.insert(v);
            greedy[it.first].insert(v);
            v.pop_back();
        }
        else if(vis[it.first] and it.first == st){
            vector<int> v1;
            v1.push_back(it.second);
            ans.insert(v1);
            greedy[it.first].insert(v1);
        }
    }
    vis[st]--;
    v.pop_back();
}
 int main() {
    int subTask,latency,i,j,k;
    set<int> forbiddenLatency,permissibleLatency;
    vector<int> v;
    cout<<"Enter number of subtasks:\n";
    cin>>subTask;
    cout<<"Enter total units of times:\n";
    cin>>times;
    int reservationTable[subTask+2][times+2];
    cout<<"Enter the reservation table(1 if process, 0 if no process)\n";
    for(i=0;i<subTask;i++){
        for(j=0;j<times;j++)
            cin>>reservationTable[i][j];
    }
    for(i=0;i<subTask;i++){
        for(j=0;j<times;j++){
            if(reservationTable[i][j]) {
                for (k = j + 1; k < times; k++) {
                    if (reservationTable[i][k]) {
                        latency = k - j;
                        forbiddenLatency.insert(latency);
                    }
                }
            }
        }
    }
    int maxi;
    auto it=forbiddenLatency.end();
    it--;
    maxi=*it;
    for(i=1;i<maxi;i++){
        if(forbiddenLatency.find(i) == forbiddenLatency.end())
            permissibleLatency.insert(i);
    }
    cout<<"The forbidden latencies are: ";
    for(auto it=forbiddenLatency.begin();it!=forbiddenLatency.end();it++)
        cout<<*it<<" ";
    cout<<endl;
    cout<<"The permissible latencies are: ";
    for(auto it=permissibleLatency.begin();it!=permissibleLatency.end();it++)
        cout<<*it<<" ";
    cout<<endl;
    for(i=1;i<=maxi;i++){
        if(permissibleLatency.find(i) != permissibleLatency.end()){
            icv = "0" + icv;
        }
        else{
            icv = "1" + icv;
        }
        highest+="1";
    }
    cout<<"The ICV is: "<<icv<<endl;
    ICV = stoi(icv , nullptr , 2);
    big = stoi(highest, nullptr, 2);
    recursion(icv,8);
    for(auto it=adj.begin();it != adj.end();it++){
        cout<<it->first.first<<" "<<it->first.second<<" -> ";
        if(it->first.first != highest)
            it->second.push_back(make_pair(icv,times));
        for(auto u: it->second){
            cout<<u.first<<" "<<u.second<<"\t";
        }cout<<endl;
    }
    findCycle(adj.begin()->first.first,adj.begin()->first.second,v);
    cout<<"Simple cycles are: ";
    for(auto it = ans.begin(); it != ans.end();it++){
        for(auto u: *it){
            cout<<u<<" ";
        }
        cout<<"\t\t";
    }cout<<endl;
    set<vector<int>> gCycle;
    for(auto &it: greedy){
        gCycle.insert(*it.second.begin());
    }cout<<"Greedy cycles are: ";
    for(auto &it: gCycle){
        for(auto u: it){
            cout<<u<<" ";
        }cout<<"\t\t";
    }cout<<endl;
    int mini = 1000000007;
    for(auto &it: gCycle){
        int sum = 0;
        for(auto u: it){
            sum += u;
        }
        sum /= it.size();
        mini = min(mini,sum);
    }
    cout<<"Minimal average latency is: "<<mini<<endl;
    return 0;
}

Answered question