/*
* Copyright (c) 2004-2010 Mellanox Technologies LTD. All rights reserved.
*
* This software is available to you under a choice of one of two
* licenses. You may choose to be licensed under the terms of the GNU
* General Public License (GPL) Version 2, available from the file
* COPYING in the main directory of this source tree, or the
* OpenIB.org BSD license below:
*
* Redistribution and use in source and binary forms, with or
* without modification, are permitted provided that the following
* conditions are met:
*
* - Redistributions of source code must retain the above
* copyright notice, this list of conditions and the following
* disclaimer.
*
* - 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.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
* BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
* ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
* CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
* SOFTWARE.
*
*/
#include "RouteSys.h"
#include "Bipartite.h"
// Helper power function
int RouteSys::myPow(int base, int pow) {
int res = 1;
for (int i=0; i<pow; i++)
res = res*base;
return res;
}
/////////////////////////////////////////////////////////////////////////////
// C'tor
RouteSys::RouteSys(int rad, int hgth, int s):radix(rad),height(hgth),step(s) {
// Calculate num in/out ports
ports = myPow(rad,height);
// Create and init ports
inPorts = new inputData[ports];
outPorts = new bool[ports];
for (int i=0; i<ports; i++) {
inPorts[i].used = false;
outPorts[i] = false;
}
// Create sub-systems
if (height > 1) {
subSys = new RouteSys* [rad];
for (int i=0; i<radix; i++)
subSys[i] = new RouteSys(rad,height-1,s+1);
}
}
//////////////////////////////////////////////////////////////////////////////
// D'tor
RouteSys::~RouteSys() {
// Just kill everything
delete[] inPorts;
delete[] outPorts;
if (height > 1) {
for (int i=0; i<radix; i++)
delete subSys[i];
delete[] subSys;
}
}
///////////////////////////////////////////////////////////////////////////////
// Add requests to the system
int RouteSys::pushRequests(vec_int req)
{
if (FabricUtilsVerboseLevel & FABU_LOG_VERBOSE)
cout << "-V- Pushing requests" << endl;
for (int i=0; i<req.size(); i++) {
// Extract comm pair
int src = i;
int dst = req[i];
if (FabricUtilsVerboseLevel & FABU_LOG_VERBOSE)
cout << "-V- Req: " << src << "->" << dst << endl;
// Check port existence
if ((src >= ports) || (dst >= ports)) {
cout << "-E- Port index exceeds num ports! Ports: " << ports << ", src: " << src << ", dst: " << dst << endl;
return 1;
}
// Check port availability
if (inPorts[src].used || outPorts[dst]) {
cout << "-E- Port already used! src: " << src << ", dst: " << dst << endl;
return 1;
}
// Mark ports as used
inPorts[src].used = true;
inPorts[src].src = src;
inPorts[src].dst = dst;
inPorts[src].inputNum = src;
inPorts[src].outNum = dst;
outPorts[dst] = true;
}
return 0;
}
/////////////////////////////////////////////////////////////////////////////
// Perform routing after requests were pushed
int RouteSys::doRouting (vec_vec_int& out)
{
// Atomic system nothing to do
if (ports == radix)
return 0;
if (FabricUtilsVerboseLevel & FABU_LOG_VERBOSE)
cout << "-V- Starting routing, step: " << step << ", height " << height << endl;
// Init the output structure
if (out.size() < ports) {
out.resize(ports);
for (int i=0; i<ports; i++) {
out[i].resize(height-1);
for (int j=0; j<height-1; j++)
out[i][j] = -1;
}
}
// We use three graph arrays for coloring
Bipartite** buff[3];
buff[0] = new Bipartite*[radix];
buff[1] = new Bipartite*[radix];
buff[2] = new Bipartite*[radix];
for (int i=0; i<radix; i++)
buff[0][i] = buff[1][i] = buff[2][i] = NULL;
// Number of colors derived through perfect matching
int matchGraphs = 0;
int currRadix = radix;
int idx = 0;
int idx_new = 1;
// Create the first graph
if (FabricUtilsVerboseLevel & FABU_LOG_VERBOSE)
cout << "-V- Ports: " << ports << ", radix: " << radix << endl;
buff[0][0] = new Bipartite(ports/radix,radix);
// Add connections
for (int i=0; i<ports; i++)
buff[0][0]->connectNodes(i/radix,inPorts[i].outNum/radix,inPorts[i]);
// Now decompose the graph to radix-1 graphs
while (1 < currRadix) {
for (int i=0; buff[idx][i] && i<radix; i++) {
// Odd radix, perfect matching is required
if (currRadix % 2) {
if (FabricUtilsVerboseLevel & FABU_LOG_VERBOSE)
cout << "-V- Perfect matching is required" << endl;
buff[2][matchGraphs] = buff[idx][i]->maximumMatch();
matchGraphs++;
}
// Now we can perform Euler decomposition
if (FabricUtilsVerboseLevel & FABU_LOG_VERBOSE)
cout << "-V- Performing Euler decompostion" << endl;
if (2*i+1 >= radix) {
cout << "-E- Graph index illegal"<< endl;
return 1;
}
buff[idx][i]->decompose(&buff[idx_new][2*i],&buff[idx_new][2*i+1]);
delete buff[idx][i];
buff[idx][i] = NULL;
}
idx = idx_new;
idx_new = (idx_new+1)%2;
currRadix = currRadix / 2;
}
// Collect all result graphs to array buff[2][i]
for (int i=matchGraphs; i<radix; i++)
buff[2][i] = buff[idx][i-matchGraphs];
// Apply decomposition results
for (int i=0; i < radix; i++) {
Bipartite* G = buff[2][i];
if (!G->setIterFirst()) {
cout << "-E- Empty graph found!" << endl;
return 1;
}
bool stop = false;
while (!stop) {
inputData d = G->getReqDat();
// Build output
if (out.size() <= d.src || out[d.src].size() <= step) {
cout << "Output index illegal" << endl;
return 1;
}
out[d.src][step] = i;
// Add request to sub-system
RouteSys* sub = subSys[i];
int inPort = d.inputNum/radix;
int outPort = d.outNum/radix;
if (sub->inPorts[inPort].used || sub->outPorts[outPort]) {
cout << "Port already used! inPort: " << inPort << ", outPort: " << outPort << endl;
return 1;
}
// Mark ports as used
sub->inPorts[inPort].used = true;
sub->inPorts[inPort].src = d.src;
sub->inPorts[inPort].dst = d.dst;
sub->inPorts[inPort].inputNum = inPort;
sub->inPorts[inPort].outNum = outPort;
outPorts[outPort] = true;
// Next request
if (!G->setIterNext()) {
stop = true;
}
}
}
// Free memory
for (int i=0; i<radix; i++)
delete buff[2][i];
delete[] buff[0];
delete[] buff[1];
delete[] buff[2];
// Run routing on sub-systems
for (int i=0; i<radix; i++) {
if (subSys[i]->doRouting(out)) {
cout << "-E- Subsystem routing failed!" << endl;
return 1;
}
}
return 0;
}