Subversion Repositories nocmodel

#!/usr/bin/env python

# -*- coding: utf-8 -*-

#

# NoC Base Objects

#

# Author:  Oscar Diaz

# Version: 0.1

# Date:    03-03-2011

#

# This code is free software; you can redistribute it and/or

# modify it under the terms of the GNU Lesser General Public

# License as published by the Free Software Foundation; either

# version 2.1 of the License, or (at your option) any later version.

#

# This code is distributed in the hope that it will be useful,

# but WITHOUT ANY WARRANTY; without even the implied warranty of

# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

# Lesser General Public License for more details.

#

# You should have received a copy of the GNU Lesser General Public

# License along with this library; if not, write to the

# Free Software  Foundation, Inc., 59 Temple Place, Suite 330,

# Boston, MA  02111-1307  USA

#

#

# Changelog:

#

# 03-03-2011 : (OD) initial release

#

"""

================

NoCmodel Base Objects

================

This module declares classes used on a Network-on-chip representation:

* NoC container class

    * Router base class

    * Channel base class

    * IPCore base class

    * Protocol base class

    * Packet class

"""

import networkx as nx

class noc(nx.Graph):

    """

    Base class for NoC modeling.

    Based on a Graph object that hold the NoC structure

    Arguments

    * kwargs: optional parameters to put as object attributes

    """

    def __init__(self, **kwargs):

        """

        NoCmodel constructor

        """

        nx.Graph.__init__(self, **kwargs)

    # objects management functions

    def add_router(self, name="", with_ipcore=False, **kwargs):

        """

        Create a base router object and add it to NoC model.

        Arguments

        * name: optional name for this router. By default has the form of

          "R_<index>"

        * with_ipcore: If True, add an ipcore to the created router.

        * kwargs: optional parameters to put as object attributes

        Return: reference to the created router object

        """

        #nodeidx = self._get_next_nodeidx()

        routernode = router(index=None, name=name, graph_ref=self, **kwargs)

        retval = self.add_router_from_object(routernode)

        if name == "":

            retval.name = "R_%d" % retval.index

        if with_ipcore:

            # kwargs are reserved for router creation, not for ipcore.

            self.add_ipcore(retval)

        return retval

    def add_router_from_object(self, router_ref):

        """

        Add an existing router object to NoC model.

        Use this function to add an object based on a derived class of

        base router defined in this module.

        Arguments

        * router_ref: reference to the router object

        Return: the same reference passed in router_ref

        Notes:

        * This function will change router_ref.index and router_ref.graph_ref

          attributes when inserted in the NoC model.

        """

        if not isinstance(router_ref, router):

            raise ValueError("Argument 'router_ref' is not a router object.")

        router_ref.index = self._get_next_nodeidx()

        router_ref.graph_ref = self

        # don't forget that index is used for address

        router_ref.address = router_ref.index

        self.add_node(router_ref.index, router_ref=router_ref)

        return router_ref

    def add_channel(self, router1, router2, name="", **kwargs):

        """

        Create a base channel object to link two objects and add it

        to NoC model.

        Arguments:

        * router1: reference to a router, router index or ipcore

        * router2: -idem-

        * name: optional argument for channel name

        * kwargs: optional parameters to put as object attributes

        Notes:

        * If router1 or router2 is an ipcore reference, this method creates

          the special channel object and update ipcore references. Additionally,

          if both arguments are ipcores, throw an error exception

        """

        if isinstance(router1, ipcore) and isinstance(router2, ipcore):

            raise ValueError("Both object references cannot be ipcore objects.")

        rhash = [None, None]

        rrefs = [None, None]

        for targetid, routertarget in enumerate((router1, router2)):

            if isinstance(routertarget, router):

                if routertarget.index in self.node:

                    rhash[targetid] = routertarget.index

                    rrefs[targetid] = self.node[routertarget.index]["router_ref"]

            elif isinstance(routertarget, ipcore):

                # special channel

                rhash[targetid] = None

                rrefs[targetid] = routertarget

            elif isinstance(routertarget, int):

                if routertarget in self.node:

                    rhash[targetid] = routertarget

                    rrefs[targetid] = self.node[routertarget]["router_ref"]

        if rrefs[0] is None:

            raise ValueError("Object not found for argument 'router1'")

        if rrefs[1] is None:

            raise ValueError("Object not found for argument 'router2'")

        if None in rhash:

            ipcore_idx = rhash.index(None)

            # ipcore channel

            if name == "":

                # channel default name format 

                name = "CH_IP_%s" % rrefs[ipcore_idx].name

            channelnode = channel(index=None, name=name, graph_ref=self, **kwargs)

        else:

            # inter-routers channel

            if name == "":

                # channel default name format 

                name = "CH_%s:%s" % (rrefs[0].name, rrefs[1].name)

            channelnode = channel(index=self._get_next_edgeidx(), name=name, graph_ref=self, **kwargs)

            self.add_edge(rhash[0], rhash[1], channel_ref = channelnode)

        channelnode.endpoints = rrefs

        return channelnode

    def add_from_channel(self, channel_ref, router1=None, router2=None):

        """

        Add a channel object to NoC model.

        Use this function to add an object based on a derived class of

        base channel defined in this module.

        Arguments

        * channel_ref: reference to the channel object

        * router1: optional reference to a router, router index or ipcore

        * router2: -idem-

        Return: the same reference passed in channel_ref

        Notes:

        * If router1 or router2 are not used as arguments, will assume that

          channel object has defined its attribute "endpoints" with the

          objects to connect. If the objects don't exist in the NoC model,

          throw an error exception.

        * If router1 or router2 is an ipcore reference, this method creates

          the special channel object and update ipcore references. Additionally,

          if both arguments are ipcores, throw an error exception.

        * This function will change channel_ref.index and channel_ref.graph_ref

          attributes when inserted in the NoC model. Also it may change

          channel_ref.endpoints with router1 and router2 references.

        """

        if not isinstance(channel_ref, channel):

            raise ValueError("Argument 'channel_ref' is not a channel object.")

        if isinstance(router1, ipcore) and isinstance(router2, ipcore):

            raise ValueError("Both object references cannot be ipcore objects.")

        rhash = [None, None]

        rrefs = [None, None]

        for targetid, routertarget in enumerate((router1, router2)):

            if isinstance(routertarget, router):

                if routertarget.index in self.node:

                    rhash[targetid] = routertarget.index

                    rrefs[targetid] = self.node[routertarget.index]["router_ref"]

            elif isinstance(routertarget, ipcore):

                # special channel

                rhash[targetid] = None

                rrefs[targetid] = routertarget

            elif isinstance(routertarget, int):

                if routertarget in self.node:

                    rhash[targetid] = routertarget

                    rrefs[targetid] = self.node[routertarget]["router_ref"]

        if (router1 is None) and (router2 is None):

            # extract from endpoints attribute

            if not hasattr(channel_ref, "endpoints"):

                raise ValueError("Channel object has not attribute 'endpoints'")

            for i in range(2):

                if not isinstance(channel_ref.endpoints[i], [router, ipcore]):

                    raise ValueError("Channel object: attribute 'endpoints'[%d] is not a router or an ipcore" % i)

                if isinstance(channel_ref.endpoints[i], router):

                    if channel_ref.endpoints[i].index in self.node:

                        rhash[i] = channel_ref.endpoints[i].index

                        rrefs[i] = channel_ref.endpoints[i]

                if isinstance(channel_ref.endpoints[i], ipcore):

                    rhash[i] = None

                    rrefs[i] = channel_ref.endpoints[i]

        if rrefs[0] is None:

            raise ValueError("Object not found for argument 'router1'")

        if rrefs[1] is None:

            raise ValueError("Object not found for argument 'router2'")

        if None in rhash:

            ipcore_idx = rhash.index(None)

            channel_ref.index = None

            # ipcore channel: adjust the references

            rrefs[ipcore_idx].channel_ref = channel_ref

            # the other reference must be a router object

            rrefs[ipcore_idx - 1].ipcore_ref = rrefs[ipcore_idx]

        else:

            # inter-routers channel

            channel_ref.index = self._get_next_edgeidx()

            self.add_edge(rhash[0], rhash[1], channel_ref=channel_ref)

        # update common references

        channel_ref.graph_ref = self

        channel_ref.endpoints = rrefs

        return channel_ref

    def add_ipcore(self, router_ref, name="", **kwargs):

        """

        Create an ipcore object and connect it to the router reference argument

        Arguments

        * router_ref: reference to an existing router

        * name: optional name for this router. By default has the form of

          "IP_<router_index>"

        * kwargs: optional parameters to put as object attributes

        Return: reference to the created ipcore object

        Notes:

        * This function automatically adds a special channel object

          (router-to-ipcore) and adjust its relations in all involved objects.

        """

        if router_ref not in self.router_list():

            raise ValueError("Argument 'router_ref' must be an existing router.")

        if name == "":

            # channel default name format 

            name = "IP_%d" % router_ref.index

        # fix channel name, based on ipcore name

        chname = "CH_%s" % name

        newip = ipcore(name=name, router_ref=router_ref, graph_ref=self, **kwargs)

        channelnode = channel(index=None, name=chname, graph_ref=self, endpoints=[router_ref, newip])

        # fix references

        newip.channel_ref = channelnode

        router_ref.ipcore_ref = newip

        return newip

    def add_from_ipcore(self, ipcore_ref, router_ref, channel_ref=None):

        """

        Add a ipcore object to NoC model.

        Arguments

        * ipcore_ref: reference to ipcore object

        * router_ref: reference to an existing router to connect

        * channel_ref: optional channel object that connect the router and

          the ipcore. If not used, this function will create a new channel object.

        Return: the same reference passed in ipcore_ref

        Notes:

        * This function automatically adds a special channel object

          (router-to-ipcore) and adjust its relations in all involved objects.

        """

        if not isinstance(ipcore_ref, ipcore):

            raise ValueError("Argument 'ipcore_ref' is not an ipcore object.")

        if router_ref not in self.router_list():

            raise ValueError("Argument 'router_ref' must be an existing router.")

        if channel_ref != None:

            if not isinstance(channel_ref, channel):

                raise ValueError("Argument 'channel_ref' is not a channel object.")

            else:

                channel_ref.index = None

                channel_ref.graph_ref = self

                channel_ref.endpoints = [router_ref, ipcore_ref]

        else:

            # channel default name format 

            chname = "CH_IP_%d" % router_ref.index

            channel_ref = channel(index=None, name=chname, graph_ref=self, endpoints=[router_ref, ipcore_ref])

        # fix references

        ipcore_ref.router_ref = router_ref

        ipcore_ref.channel_ref = channel_ref

        ipcore_ref.graph_ref = self

        router_ref.ipcore_ref = ipcore_ref

        return ipcore_ref

    def del_router(self, router_ref):

        """

        Remove router_ref from the NoC model

        TODO: not implemented

        """

        pass

    def del_channel(self, channel_ref):

        """

        Remove channel_ref from the NoC model

        TODO: not implemented

        """

        pass

    def del_ipcore(self, ipcore_ref):

        """

        Remove ipcore_ref from the NoC model

        TODO: not implemented

        """

        pass

    # list generation functions

    def router_list(self):

        l = []

        for i in self.nodes_iter(data=True):

            l.append(i[1]["router_ref"])

        return l

    def ipcore_list(self):

        l = []

        for i in self.nodes_iter(data=True):

            if i[1]["router_ref"].ipcore_ref != None:

                l.append(i[1]["router_ref"].ipcore_ref)

        return l

    def channel_list(self):

        # this function does not list ipcore channels

        l = []

        for i in self.edges_iter(data=True):

            l.append(i[2]["channel_ref"])

        return l

    def all_list(self):

        l = self.router_list()

        l.extend(self.ipcore_list())

        l.extend(self.channel_list())

        return l

    # query functions

    def get_router_by_address(self, address):

        for r in self.router_list():

            if r.address == address:

                return r

        return False

    # hidden functions

    def _add_router_from_node(self, node, name="", router_ref=None, **kwargs):

        """

        Create a router object (or use an existing router reference) based on

        an existing empty node on graph object.

        """

        if router_ref is None:

            # index comes from node

            if name == "":

                name = "R_%d" % node

            routernode = router(index=node, name=name, graph_ref=self, **kwargs)

        else:

            if not isinstance(router_ref, router):

                raise ValueError("Argument 'router_ref' is not a router object.")

            routernode = router_ref

            routernode.index = node

            routernode.graph_ref = self

        self.node[node]["router_ref"] = routernode

        return routernode

    def _add_channel_from_edge(self, edge, name="", channel_ref=None, **kwargs):

        """

        Create a channel object (or use an existing channel reference) based

        on an existing edge on graph object.

        """

        # inter-routers channels only

        rrefs = [self.node[edge[0]]["router_ref"], self.node[edge[1]]["router_ref"]]

        chindex = self.edges().index(edge)

        if channel_ref is None:

            if name == "":

                # channel default name format 

                name = "CH_%s:%s" % (rrefs[0].name, rrefs[1].name)

            channelnode = channel(index=chindex, name=name, graph_ref=self, **kwargs)

        else:

            if not isinstance(channel_ref, channel):

                raise ValueError("Argument 'channel_ref' is not a channel object.")

            channelnode = channel_ref

            channelnode.index = chindex

            channelnode.graph_ref = self

        channelnode.endpoints = rrefs

        self.get_edge_data(edge[0], edge[1])["channel_ref"] = channelnode

        return channelnode

    def _get_next_nodeidx(self):

        # get the next node index number

        # don't use intermediate available indexes

        return len(self.nodes())

    def _get_next_edgeidx(self):

        # get the next edge index number

        # don't use intermediate available indexes

        return len(self.edges())

# *******************************

# Generic models for NoC elements

# *******************************

class nocobject():

    """

    NoC base object

    This base class is used to implement common methods for NoC objects.

    Don't use directly.

    """

    def get_protocol_ref(self):

        """

        Get protocol object for this instance

        """

        if hasattr(self, "protocol_ref"):

            if isinstance(self.protocol_ref, protocol):

                return self.protocol_ref

        if isinstance(self.graph_ref.protocol_ref, protocol):

            return self.graph_ref.protocol_ref

        # nothing?

        return None

class ipcore(nocobject):

    """

    IP core base object

    This object represents a IP Core object and its properties. This base class

    is meant to either be inherited or extended by adding other attributes.

    Relations with other objects:

    * It should be related to one NoC model object (self.graph_ref)

    * It should have one reference to a router object (self.router_ref), even if

      the ipcore has a direct connection to the NoC.

    * It should have one reference to a channel object (self.channel_ref). This

      channel exclusively link this ipcore and its router.

    Attributes:

    * name

    * router_ref: optional reference to its related router.

    * channel_ref: optional reference to its related channel

    * graph_ref: optional reference to its graph model

    """

    def __init__(self, name, **kwargs):

        # Basic properties

        self.name = name

        # default values

        self.router_ref = None

        self.channel_ref = None

        self.graph_ref = None

        for key in kwargs.keys():

            setattr(self, key, kwargs[key])

class router(nocobject):

    """

    Router base object

    This object represents a router object and its properties. This base class

    is meant to either be inherited or extended by adding other attributes.

    Relations with other objects:

    * It should be related to one NoC model object (self.graph_ref)

    * It should be one of the node attributes in the graph model

      (node["router_ref"])

    * It may have one reference to an ipcore object (self.ipcore_ref)

    * It has a port list with relations to other routers through channel objects,

      and only one relation to its ipcore object through one channel.

      (self.ports). Note that this attribute must be updated after changing

      the NoC model.

    Attributes:

    * index: index on a noc object. Essential to search for a router object

    * name

    * ipcore_ref: optional reference to its related ipcore

    * graph_ref: optional reference to its graph model

    """

    def __init__(self, index, name, **kwargs):

        # Basic properties

        self.index = index

        self.name = name

        # default values

        self.ipcore_ref = None

        self.graph_ref = None

        # address can be anything, but let use index by default

        # note that address can be overriden with optional arguments in kwargs

        self.address = index

        for key in kwargs.keys():

            setattr(self, key, kwargs[key])

        # ports structure

        self.ports = {}

        # available routes info

        self.routes_info = {}

    # update functions: call them when the underlying NoC structure

    # has changed

    def update_ports_info(self):

        """

        Update the dictionary "ports": information about router neighbors,

        the channels that connect them and its references.

        Ports dictionary has the following structure:

        * key: address of the neighbor router that this port connects.

        * value: dictionary with the following keys:

            * "peer" (required): reference to the neighbor router

            * "channel" (required): reference to the channel that connects this

              router and its neighbor router.

            * Optional keys can be added to this dictionary.

        * Also, the special key "local address" holds the port to

          router's ipcore. Its values are:

            * "peer" (required): reference to its ipcore

            * "channel" (required): reference to the channel that connects this

              router and its ipcore.

            * Optional keys can be added to this dictionary with the same

              meaning as other ports.

        """

        # port definitions

        localhash = self.address

        updated_addr = [self.address]

        for neighborhash in self.graph_ref.neighbors(localhash):

            neighbor = self.graph_ref.node[neighborhash]["router_ref"]

            #check if already defined in ports dictionary

            if neighbor.address not in self.ports:

                self.ports[neighbor.address] = {}

            # update relevant data

            self.ports[neighbor.address]["peer"] = neighbor

            ch_ref = self.graph_ref.edge[localhash][neighborhash]["channel_ref"]

            self.ports[neighbor.address]["channel"] = ch_ref

            updated_addr.append(neighbor.address)

        # special port: ipcore

        if self.address not in self.ports:

            self.ports[self.address] = {}

        self.ports[self.address]["peer"] = self.ipcore_ref

        # take channel reference from ipcore. Other channels are related to

        # an edge on the graph model. Channels in an ipcore are special because

        # they don't have a related edge, just link an ipcore and this router

        self.ports[self.address]["channel"] = self.ipcore_ref.channel_ref

        # clean 'deleted' ports

        keys = self.ports.iterkeys()

        for deleted in keys:

            if deleted not in updated_addr:

                del self.ports[deleted]

    def update_routes_info(self):

        """

        Update the dictionary "routes_info": it is a table with information

        about how a package, starting from this router, can reach another one.

        routes_info dictionary has the following structure:

        * keys : the address of all the routers in NoC

        * values : an ordered list of dictionaries with

            * "next" : address of the next router

            * "paths" : list of possible paths for key destination

        """

        # this function will calculate a new table!

        self.routes_info.clear()

        #mynodehash = (self.coord_x, self.coord_y)

        mynodehash = self.index

        for destrouter in self.graph_ref.router_list():

            # discard route to myself

            if destrouter == self:

                continue

            #desthash = (destrouter.coord_x, destrouter.coord_y)

            desthash = destrouter.index

            # entry for destrouter

            self.routes_info[destrouter.index] = []

            # first: take all shortest paths (function not available on NetworkX)

            shortest_routes = all_shortest_paths(self.graph_ref, mynodehash, desthash)

            # convert nodehashes to router addresses

            shortest_r_addr = [map(lambda x : self.graph_ref.node[x]["router_ref"].address, i) for i in shortest_routes]

            # NOTE about routing tables: need to think about which routes based on 

            # shortest paths are better in general with other routers, so the links

            # are well balanced. A possible problem could be that some links will carry

            # more data flow than others.

            # A possible workaround lies in the generation of routing tables at

            # NoC level, taking account of neighbors tables and others parameters.

            # extract the next neighbor in each path

            for route in shortest_r_addr:

                # first element is myself, last element is its destination. 

                # for this routing table, we only need the next router to

                # send the package.

                newroute = True

                for route_entry in self.routes_info[destrouter.index]:

                    if route[1] == route_entry["next"]:

                        # another route which next element was taken account

                        route_entry["paths"].append(route)

                        newroute = False

                if newroute:

                    self.routes_info[destrouter.index].append({"next": route[1], "paths": [route]})

            # last option: send through another node not in the shortest paths 

            # NOTE: decide if this is needed or make sense

class channel(nocobject):

    """

    Channel base object

    This object represents a channel object and its properties. This base class

    is meant to either be inherited or extended by adding other attributes.

    Relations with other objects:

    * It should be related to one NoC model object (self.graph_ref)

    * It may be one of the edge attributes in the graph model

      (edge["channel_ref"]). In this case, this channel connects two routers

      in the NoC model.

    * It should have two references to NoC objects (self.endpoints). Two options

      exists: two routers references (channel has an edge object) or, one

      router and one ipcore (channel don't have any edge object).

    Attributes:

    * name

    * index: optional index on a noc object. Must have an index when it has

      a related edge in the graph model (and allowing it to be able to do

      channel searching). None means it is an ipcore related channel

    * graph_ref optional reference to its graph model

    * endpoints optional two-item list with references to the connected objects

    """

    def __init__(self, name, index=None, **kwargs):

        # Basic properties

        self.index = index

        self.name = name

        # Default values

        self.graph_ref = None

        self.endpoints = [None, None]

        for key in kwargs.keys():

            setattr(self, key, kwargs[key])

    def is_ipcore_link(self):

        """

        Checks if this channel is a special link for an ipcore.

        Return: True if the channel is related to an ipcore

        """

        # Search for ipcore in endpoints. Don't check None on self.index.

        for ref in self.endpoints:

            if isinstance(ref, ipcore):

                return True

        return False

class protocol(nocobject):

    """

    Protocol base object

    This object represents the protocol that the NoC objects use. This

    object has attributes that define the protocol used, mainly it can be

    used to generate, encode, decode or interpret packets on the NoC.

    This base class can be either be inherited or extended by adding

    other attributes.

    Relations with other objects:

    * Each object on the NoC (routers, channels and ipcores) may have

      one reference to a protocol object (object.protocol_ref)

    * A NoC model may have a protocol object: in this case, all objects in

      the model will use this protocol (nocmodel.protocol_ref)

    * A protocol object is a generator of packet objects

    Attributes:

    * name

    Notes:

    * Optional arguments "packet_format" and "packet_order" can be

      added at object construction, but will not check its data consistency.

      At the moment, we recommend using update_packet_field() method to

      fill this data structures.

    """

    def __init__(self, name="", **kwargs):

        """

        Constructor

        Notes:

        * Optional arguments will be added as object attributes.

        """

        # NOTE: to avoid python version requirements (2.7), implement ordered 

        # dict with an additional list. When we are sure of using 

        # Python > 2.7 , change to collections.OrderedDict

        self.name = name

        self.packet_format = {}

        self.packet_order = []

        self.packet_class = packet

        for key in kwargs.keys():

            setattr(self, key, kwargs[key])

    def get_protocol_ref(self):

        # override to use myself

        return self

    def update_packet_field(self, name, type, bitlen, description=""):

        """

        Add or update a packet field.

        Arguments

        * name