[parsec-users] Canneal speed up loading patch

kishore kumar kishoreguptaos at gmail.com
Wed Jan 25 15:52:42 EST 2012


I have observed that the loading phases (only main thread) of canneal,
blackscholes, and dedup takes 75% to 95% of the total turn-around time of
these programs. Worker threads contribute a little. Minimizing this loading
phase is really useful for scalability studies.

Best,
Kishore Kumar Pusukuri
http://www.cs.ucr.edu/~kishore



On Wed, Jan 25, 2012 at 11:42 AM, Mark Roth <mroth at sfu.ca> wrote:

> 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
> _______________________________________________
> parsec-users mailing list
> parsec-users at lists.cs.princeton.edu
> https://lists.cs.princeton.edu/mailman/listinfo/parsec-users
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cs.princeton.edu/pipermail/parsec-users/attachments/20120125/89d5964e/attachment-0001.html>


More information about the parsec-users mailing list