[parsec-users] Canneal speed up loading patch

Mark Roth mroth at sfu.ca
Tue Jan 24 23:05:26 EST 2012


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


More information about the parsec-users mailing list