[parsec-users] Canneal speed up loading patch

Jim Dempsey jim at quickthreadprogramming.com
Wed Jan 25 08:51:00 EST 2012


>> 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



More information about the parsec-users mailing list