[parsec-users] Canneal speed up loading patch

Mark Roth mroth at sfu.ca
Wed Jan 25 14:42:44 EST 2012


I looked into the feasibility of pipelining this section. However, the
majority of the time is spent doing  map lookup's and insertions. The
time savings was a result of changing the key of the std::map from a
string to an integer. Further savings can be had by removing the need
for std::map entirely.

Conversion of node name directly to index requires changing input
files in order to avoid gaps in the labeling.

Anyways, I just thought that this would help out for people who need
to run Canneal a bunch of times as the loading phase becomes the
dominate time factor when running in parallel.

- Mark

On Wed, Jan 25, 2012 at 5:51 AM, Jim Dempsey
<jim at quickthreadprogramming.com> wrote:
>>> integer id value. It relies on the node names in the input file to lower
> case alphabetic character of length 6 or less...using the node index as the
> name in the input file
>
> Then the input file is application dependant. Conversion time to id should
> be immaterial. Assume 5 bits used for encoded character, you do not need a
> case conversion. For uncased conversion a simple ch&31 produces the
> converted character. As for input file size, your key is 4 bytes. If the
> average name is 3 (+1 for seperator) then the storage size is a wash.
>
> Time would be better gained by pipelining the input with the processing.
>
> Jim Dempsey
>
>
> -----Original Message-----
> From: parsec-users-bounces at lists.cs.princeton.edu
> [mailto:parsec-users-bounces at lists.cs.princeton.edu] On Behalf Of Mark Roth
> Sent: Tuesday, January 24, 2012 10:05 PM
> To: PARSEC Users
> Subject: [parsec-users] Canneal speed up loading patch
>
> This patch speeds up the serial loading process of canneal by approximately
> 30% (about 10 seconds on my machine for native input).
> It changes the hashmap name look up from a string to an integer id value. It
> relies on the node names in the input file to lower case alphabetic
> character of length 6 or less (sim native only contains length 5 or less).
> Final routing costs have been verified to match after the patch.
>
> However, using the node index as the name in the input file would probably
> be better in the long run to improve load times.
>
> - Mark
>
> <<<<< Begin Patch >>>>>>>
> From 65d13bdfa0462b1462c645259b1022b5dbb79a10 Mon Sep 17 00:00:00 2001
> From: Mark Roth <mr.mark.roth at gmail.com>
> Date: Mon, 23 Jan 2012 23:51:49 -0800
> Subject: [PATCH] Changed name field of hashmap from string to uint.
>
> ---
>  netlist.cpp    |   30 ++++++++++++++++++++++--------
>  netlist.h      |    6 +++---
>  netlist_elem.h |    5 ++---
>  3 files changed, 27 insertions(+), 14 deletions(-)
>
> diff --git a/netlist.cpp b/netlist.cpp
> index bd1d77c..e076df9 100644
> --- a/netlist.cpp
> +++ b/netlist.cpp
> @@ -51,7 +51,7 @@ void netlist::release(netlist_elem* elem)  routing_cost_t
> netlist::total_routing_cost()  {
>        routing_cost_t rval = 0;
> -       for (std::map<std::string, netlist_elem*>::iterator iter =
> _elem_names.begin();
> +       for (std::map<unsigned int, netlist_elem*>::iterator iter =
> _elem_names.begin();
>                 iter != _elem_names.end();
>                 ++iter){
>                netlist_elem* elem = iter->second;
> @@ -145,11 +145,23 @@ netlist_elem*
> netlist::netlist_elem_from_loc(location_t& loc)
>
> //**************************************************************************
> ***************
>  //
>
> //**************************************************************************
> ***************
> -netlist_elem* netlist::netlist_elem_from_name(std::string& name)
> +netlist_elem* netlist::netlist_elem_from_name(unsigned int name)
>  {
>        return (_elem_names[name]);
>  }
>
> +inline unsigned int id_from_name(std::string &name) {
> +       // map node id from 'abcde' to base 32 representation
> +       // assumes node id's are lowercase alpha numeric of size 6 or less
> +       // allows for input up to size 300M; Sim Native is of size 2.5M
> +       unsigned int id = 0;
> +       for (int i = 0; i < name.length(); i++) {
> +               id = id<<5;
> +               id += ((int)name.at(i) - 97 + 1); // ascii('a') == 97
> +       }
> +       return id;
> +}
> +
>
> //**************************************************************************
> ***************
>  //  TODO add errorchecking
>  // ctor.  Takes a properly formatted input file, and converts it into a @@
> -193,11 +205,12 @@ netlist::netlist(const std::string& filename)
>                }
>                std::string name;
>                fin >> name;
> -               netlist_elem* present_elem = create_elem_if_necessary(name);
> // the
> element that we are presently working on
> +               unsigned int id = id_from_name(name);
> +               netlist_elem* present_elem = create_elem_if_necessary(id);
> // the
> element that we are presently working on
>                //use create if necessary because it might have been created
> as a previous elements fanin
>
>                //set the basic info for the element
> -               present_elem->item_name = name; //its name
> +               present_elem->item_name = id; //its name
>
>                int type; //its type TODO errorcheck here
>                fin >> type; // presently, don't actually use this @@ -207,7
> +220,8 @@ netlist::netlist(const std::string& filename)
>                        if (fanin_name == "END"){
>                                break; //last element in fanin
>                        } //otherwise, make present elem the fanout of
> fanin_elem, and vice versa
> -                       netlist_elem* fanin_elem =
> create_elem_if_necessary(fanin_name);
> +                       unsigned int fanin_id = id_from_name(fanin_name);
> +                       netlist_elem* fanin_elem =
> create_elem_if_necessary(fanin_id);
>                        present_elem->fanin.push_back(fanin_elem);
>                        fanin_elem->fanout.push_back(present_elem);
>                }//while (fin >> fanin_name)
> @@ -219,12 +233,12 @@ netlist::netlist(const std::string& filename)  // Used
> in the ctor.  Since an element have fanin from an element that can occur
> both  // earlier and later in the input file, we must handle both cases
>
> //**************************************************************************
> ***************
> -netlist_elem* netlist::create_elem_if_necessary(std::string& name)
> +netlist_elem* netlist::create_elem_if_necessary(unsigned int name)
>  {
>        static unsigned unused_elem = 0;//the first unused element
>        netlist_elem* rval;
>        //check whether we already have a netlist element with that name
> -       std::map<std::string, netlist_elem*>::iterator iter =
> _elem_names.find(name);
> +       std::map<unsigned int, netlist_elem*>::iterator iter =
> +_elem_names.find(name);
>        if (iter == _elem_names.end()){
>                rval = &_elements.at(unused_elem);//if not, get one from the
> _elements pool
>                _elem_names[name] = rval;//put it in the map @@ -245,7
> +259,7 @@ void netlist::print_locations(const std::string& filename)
>        ofstream fout(filename.c_str());
>        assert(fout.is_open());
>
> -       for (std::map<std::string, netlist_elem*>::iterator iter =
> _elem_names.begin();
> +       for (std::map<unsigned int, netlist_elem*>::iterator iter =
> _elem_names.begin();
>                 iter != _elem_names.end();
>                 ++iter){
>                netlist_elem* elem = iter->second;
> diff --git a/netlist.h b/netlist.h
> index 1f51923..5720e67 100644
> --- a/netlist.h
> +++ b/netlist.h
> @@ -50,7 +50,7 @@ public:
>        void swap_locations(netlist_elem* elem_a, netlist_elem* elem_b);
>        void shuffle(Rng* rng);
>        netlist_elem* netlist_elem_from_loc(location_t& loc);
> -       netlist_elem* netlist_elem_from_name(std::string& name);
> +       netlist_elem* netlist_elem_from_name(unsigned int name);
>        routing_cost_t total_routing_cost();
>        void print_locations(const std::string& filename);
>        void release(netlist_elem* elem);
> @@ -63,8 +63,8 @@ protected:
>        unsigned _chip_size;
>        std::vector<netlist_elem> _elements;//store the actual elements here
>        std::vector< std::vector<location_t> > _locations;//store the actual
> locations here
> -       std::map<std::string, netlist_elem*> _elem_names;
> -       netlist_elem* create_elem_if_necessary(std::string& name);
> +       std::map<unsigned int, netlist_elem*> _elem_names;
> +       netlist_elem* create_elem_if_necessary(unsigned int name);
>        //due to the pointers, perhaps I should make the copy operator
> protected to prevent copying  };
>
> diff --git a/netlist_elem.h b/netlist_elem.h index a79d4b6..f5814f0 100644
> --- a/netlist_elem.h
> +++ b/netlist_elem.h
> @@ -29,8 +29,7 @@
>
>  #ifndef NETLIST_ELEM_H
>  #define NETLIST_ELEM_H
> -
> -#include <string>
> +#include <string> // need to leave this in to define NULL
>  #include <vector>
>
>  #include "AtomicPtr.h"
> @@ -46,7 +45,7 @@ public:
>        routing_cost_t swap_cost(location_t* old_loc, location_t* new_loc);
>
>  public:
> -       std::string item_name;
> +       unsigned int item_name;
>        std::vector<netlist_elem*> fanin;
>        std::vector<netlist_elem*> fanout;
>        AtomicPtr<location_t> present_loc;
> --
> 1.7.5.4
> _______________________________________________
> parsec-users mailing list
> parsec-users at lists.cs.princeton.edu
> https://lists.cs.princeton.edu/mailman/listinfo/parsec-users
>
> _______________________________________________
> parsec-users mailing list
> parsec-users at lists.cs.princeton.edu
> https://lists.cs.princeton.edu/mailman/listinfo/parsec-users


More information about the parsec-users mailing list