From a321a5c412090d04dfaea4b4876c4901c42cfe44 Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Wed, 27 Feb 2013 09:32:19 +0100 Subject: Moved stand-alone libs to libs/ directory and added libs/subcircuit --- libs/subcircuit/Makefile | 52 ++ libs/subcircuit/README | 440 ++++++++++++++ libs/subcircuit/demo.cc | 134 +++++ libs/subcircuit/scshell.cc | 235 ++++++++ libs/subcircuit/subcircuit.cc | 1264 +++++++++++++++++++++++++++++++++++++++ libs/subcircuit/subcircuit.h | 139 +++++ libs/subcircuit/test_large.spl | 221 +++++++ libs/subcircuit/test_macc22.txt | 48 ++ libs/subcircuit/test_perm.pl | 108 ++++ libs/subcircuit/test_shorts.spl | 121 ++++ 10 files changed, 2762 insertions(+) create mode 100644 libs/subcircuit/Makefile create mode 100644 libs/subcircuit/README create mode 100644 libs/subcircuit/demo.cc create mode 100644 libs/subcircuit/scshell.cc create mode 100644 libs/subcircuit/subcircuit.cc create mode 100644 libs/subcircuit/subcircuit.h create mode 100644 libs/subcircuit/test_large.spl create mode 100644 libs/subcircuit/test_macc22.txt create mode 100644 libs/subcircuit/test_perm.pl create mode 100644 libs/subcircuit/test_shorts.spl (limited to 'libs/subcircuit') diff --git a/libs/subcircuit/Makefile b/libs/subcircuit/Makefile new file mode 100644 index 00000000..af745b4b --- /dev/null +++ b/libs/subcircuit/Makefile @@ -0,0 +1,52 @@ + +CONFIG := clang-debug +# CONFIG := gcc-debug +# CONFIG := profile +# CONFIG := release + +CC = clang +CXX = clang +CXXFLAGS = -MD -Wall -Wextra -ggdb +LDLIBS = -lstdc++ + +ifeq ($(CONFIG),clang-debug) +CXXFLAGS += -std=c++11 -O0 +endif + +ifeq ($(CONFIG),gcc-debug) +CC = gcc +CXX = gcc +CXXFLAGS += -std=gnu++0x -O0 +endif + +ifeq ($(CONFIG),profile) +CC = gcc +CXX = gcc +CXXFLAGS += -std=gnu++0x -Os -DNDEBUG +endif + +ifeq ($(CONFIG),release) +CC = gcc +CXX = gcc +CXXFLAGS += -std=gnu++0x -march=native -O3 -DNDEBUG +endif + +all: demo scshell + +demo: demo.o subcircuit.o + +scshell: scshell.o subcircuit.o + +test: scshell + ./scshell < test_macc22.txt + perl test_perm.pl | ./scshell + splrun test_shorts.spl | ./scshell + splrun test_large.spl | ./scshell + +clean: + rm -f demo scshell *.o *.d + +.PHONY: all test clean + +-include *.d + diff --git a/libs/subcircuit/README b/libs/subcircuit/README new file mode 100644 index 00000000..5c8a8a9e --- /dev/null +++ b/libs/subcircuit/README @@ -0,0 +1,440 @@ + + ************************************************************************** + * * + * The SubCircuit C++11 library * + * * + * An implementation of a modified Ullmann Subgraph Isomorphism Algorithm * + * for coarse grain logic networks. by Clifford Wolf * + * * + ************************************************************************** + +============ +Introduction +============ + +This is a library that implements a modified Ullmann Subgraph Isomorphism +Algorithm with additional features aimed at working with coarse grain logic +networks. + +A simple command line tool that exposes the features of the library is also +included. + + +Under-Construction Warning +-------------------------- + +This work is under constructions. It is likely that they are bugs in the +library that need fixing. Feel free to contact me at clifford@clifford.at +if you have found a bug. + + +C++11 Warning +------------- + +This project is written in C++11. Use appropriate compiler switches to compile +it. Tested with clang version 3.0 and option -std=c++11. Also tested with gcc +version 4.6.3 and option -std=c++0x. + + +======== +Features +======== + +The input is two graphs (needle and haystack) that represent coarse grain +logic networks. The algorithm identifies all subgraphs of haystack that are +isomorphic to needle. + +The following additional features over the regular Ullmann Subgraph Isomorphism +Algorithm are provided by the library. + + * The graphs are attributed hypergraphs capable of representing netlists: + + - Nodes represent the logic cells: + - Nodes have types and only match compatible types + - Nodes have ports with variable bit-width + + - Hyperedges represent the signals: + - Each hyperedge connects one to many bits on ports on nodes + + - Callback functions for advanced attributes and compatibility rules: + Any set of node-node compatibility rules and edge-edge + compatibility rules can be implemented by providing + the necessary callback functions. + + * The algorithm is very efficient when all or many bits of one port are + connected to bits of the same other port. This is usually the case + in coarse grain logic networks. But the algorithm does not add any + restrictions in this area; it is just optimized for this scenario. + + * The algorithm can be configured to allow larger ports in needle cells to + match smaller ports in haystack cells in certain situations. This way it + is possible to e.g. have a 32-bit adder cell in the needle match a + 16-bit adder cell in the haystack. + + * The algorithm can be configured to perform port-swapping on certain + ports on certain cell types to match commutative operations properly. + + This is, however, not implemented very efficiently when a larger number + of permutations is possible on a cell type. Therefore it is recommended + to only use swap groups with only a few members and a few such groups + on one cell type type. + + Also note, that the algorithm can not resolve complex dependencies + between the port swappings of different cells. Therefore it is + recommended to only use port swapping on input pins of commutative + operations, where such complex dependencies can not emerge. + + * The algorithm can be configured to distinguish between internal signals + of the needle and externally visible signals. The needle will only + match a subgraph of the haystack if that subgraph does not expose the + internal signal to nodes in the haystack outside the matching subgraph. + + * The algorithm can recognize a subcircuit even if some or all of its + inputs and/or outputs are shorted together. + + * Explicit fast support for constant signals without extra nodes for + constant drivers. + + * Support for finding only non-overlapping matches. + + * The public API of the library is using std::string identifiers for + nodes, node types and ports. Internally the costly part of the + algorithm is only using integer values, thus speeding up the + algorithm without exposing complex internal encodings to the caller. + + +================= +API Documentation +================= + +This section gives a brief overview of the API. For a working example, have a +look at the demo.cc example program in this directory. + + +Setting up graphs +----------------- + +Instanciate the SubCircuit::Graph class and use the methods of this class to +set up the circuit. + + SubCircuit::Graph myGraph; + +For each node in the circuit call the createNode() method. Specify the +identifier for the node and also the type of function implemented by the node. +Then call createPort() for each port of this node. + +E.g. the following code adds a node "myAdder" of type "add" with three 32 bit +wide ports "A", "B" and "Y". Note that SubCircuit does not care which port is +an input and which port is an output. The last (and optional) argument to +createPort() specifies the minimum number of bits required for this port in the +haystack (this field is only used in the needle graph). So in this example the +node would e.g. also match any adder with a bit width smaller 32. + + myGraph.createNode("myAdder", "add"); + myGraph.createPort("myAdder", "A", 32, 1); + myGraph.createPort("myAdder", "B", 32, 1); + myGraph.createPort("myAdder", "Y", 32, 1); + +The createConnection() method can be used to connect the nodes. It internally +creates a hypergraph. So the following code does not only connect cell1.Y with +cell2.A and cell3.A but also implicitly cell2.A with cell3.A. + + myGraph.createConnection("cell1", "Y", "cell2", "A"); + myGraph.createConnection("cell1", "Y", "cell3", "A"); + +Redundent calls to createConnection() are ignored. As long as the method is +called after the relevant nodes and ports are created, the order in which the +createConnection() calls are performed is irrelevant. + +The createConnection() method can also be used to connect single bit signals. +In this case the start bit for both ports must be provided as well as an +optional width (which defaults to 1). E.g. the following calls can be used to +connect the 32 bit port cell4.Y to the 32 bit port cell5.A with a one bit left +rotate shift, + + myGraph.createConnection("cell4", "Y", 0, "cell5", "A", 1, 31); + myGraph.createConnection("cell4", "Y", 31, "cell5", "A", 0); + +The method createConstant() can be used to add a constant driver to a signal. +The signal value is encoded as one char by bit, allowing for multi-valued +logic matching. The follwoing command sets the lowest bit of cell6.A to a +logic 1: + + myGraph.createConnection("cell6", "A", 0, '1'); + +It is also possible to set an entire port to a integer value, using the +encodings '0' and '1' for the binary digits: + + myGraph.createConnection("cell6", "A", 42); + +The method markExtern() can be used to mark a signal as externally visible. In +a needle graph this means, this signal may match a signal in the haystack that +is used outside the matching subgraph. In a haystack graph this means, this +signal is used outside the haystack graph. I.e. an internal signal of the +needle won't match an external signal of the haystack regardless where the +signal is used in the haystack. + +In some application one may disable this extern/intern checks. This can easily +be achieved by marking all signals in the needle as extern. This can be done +using the Graph::markAllExtern() method. + + +Setting up and running solvers +------------------------------ + +To actually run the subgraph isomorphism algorithm, an instance of +SubCircuit::Solver must be created. + + SubCircuit::Solver mySolver; + +The addGraph() method can be used to register graphs with the solver: + + mySolver.addGraph("graph1", myGraph); + mySolver.addGraph("graph2", myOtherGraph); + +Usually nodes in the needle and the haystack must have the same type identifier +to match each other. Additionally pairs of compatible needle and haystack node +pairs can be registered using the addCompatibleTypes() method: + + mySolver.addCompatibleTypes("alu", "add"); + mySolver.addCompatibleTypes("alu", "sub"); + mySolver.addCompatibleTypes("alu", "and"); + mySolver.addCompatibleTypes("alu", "or"); + mySolver.addCompatibleTypes("alu", "xor"); + +Note that nodes in needle and haystack must also use the same naming convention +for their ports in order to be considered compatible by the algorithm. + +Similarly the method addCompatibleConstants() can be used the specify which +constant values in the needle should match which constant value in the haystack. +Equal values always do match. + + mySolver.addCompatibleConstants('x', '0'); + mySolver.addCompatibleConstants('x', '1'); + +Some cells implement commutative operations that don't care if their input +operands are swapped. For this cell types it is possible to register groups +of swappable ports. Let's consider a cell "macc23" that implements the +function Y = (A * B) + (C * D * E): + + mySolver.addSwappablePorts("macc23", "A", "B"); + mySolver.addSwappablePorts("macc23", "C", "D", "E"); + +Sometimes the rules for port swapping are a more complicated and the swapping +of one port is related to the swapping of another port. Let's consider a cell +"macc22" that implements the function Y = (A * B) + (C * D): + + mySolver.addSwappablePorts("macc22", "A", "B"); + mySolver.addSwappablePorts("macc22", "C", "D"); + + std::map portMapping; + portMapping["A"] = "C"; + portMapping["B"] = "D"; + portMapping["C"] = "A"; + portMapping["D"] = "B"; + mySolver.addSwappablePortsPermutation("macc22", portMapping); + +I.e. the method mySolver.addSwappablePortsPermutation() can be used to register +additional permutations for a node type of which one or none is applied on top +of the permutations yielded by the permutations generated by the swap groups. + +Note that two solutions that differ only in the applied port swapping are not +reported as separate solutions. Instead only one of them is selected (in most +cases the one with less port swapping as it is usually identified first). + +Once everything has been set up, the solve() method can be used to actually +search for isomorphic subgraphs. The first argument to solve() is an +std::vector objects to which all found solutions +are appended. The second argument is the identifier under which the needle +graph has been registered and the third argument is the identifier under which +the haystack graph has been registered: + + std::vector results; + mySolver.solve(results, "graph1", "graph2"); + +The SubCircuit::Solver::Result object is a simple data structure that contains +the mappings between needle and haystack nodes, port mappings after the port +swapping and some additional metadata. See "subcircuit.h" and "demo.cc" for +details. + +The solve() method has a third optional boolean argument. If it is set to +false, solve will not return any solutions that contain haystack nodes that +have been part of a previously found solution. This way it is e.g. easy +to implement a greedy macro cell matching algorithm: + + std::vector results; + mySolver.solve(results, "macroCell1", "circuit", false); + mySolver.solve(results, "macroCell2", "circuit", false); + mySolver.solve(results, "macroCell3", "circuit", false); + +After this code has been executed, the results vector contains all +non-overlapping matches of the three macrocells. The method +clearOverlapHistory() can be used to reset the internal state used +for this feature. The default value for the third argument to solve() +is true (allow overlapping). + +The solve() method also has a fourth optional integer argument. If it is set to +a positive integer, this integer specifies the maximum number of solutions to +be appended to the results vector, i.e. to terminate the algorithm early when +the set number of matches is found. When this fourth argument is negative or +omitted all matches are found and appended. + +An alternative version of the solve() method supports an additional argument +after they haystack graph identifier that specifies initial mappings for +the algorithm. In the following example only the haystack nodes cell_1 and +cell_2 are considered as mappings for the needle node cell_A: + + std::map> initialMappings; + initialMappings["cell_A"].insert("cell_1"); + initialMappings["cell_A"].insert("cell_2"); + + std::vector results; + mySolver.solve(results, "graph1", "graph2", initialMappings); + +The clearConfig() method can be used to clear all data registered using +addCompatibleTypes(), addCompatibleConstants(), addSwappablePorts() and +addSwappablePortsPermutation() but retaining the graphs and the overlap state. + + +Using user callback function +---------------------------- + +For more complex tasks it is possible to derive a class from SubCircuit::Solver +that overloads one or more of the following virtual methods. The userData +arguments to the following methods are void pointers that can be passed as +third argument to Graph::createNode() and are simly passed thru to the user +callback functions together with the node id whenever a node is referenced. + +bool userCompareNodes(needleGraphId, needleNodeId, needleUserData, haystackGraphId, haystackNodeId, haystackUserData): + + Perform additional checks on a pair of nodes (one from the needle, one + from the haystack) to determine if the nodes are compatible. The default + implementation always returns true. + + +bool userCompareEdge(needleGraphId, needleFromNodeId, needleFromUserData, needleToNodeId, needleToUserData, + haystackGraphId, haystackFromNodeId, haystackFromUserData, haystackToNodeId, haystackToUserData): + + Perform additional checks on a pair of a pair of adjacent nodes (one + adjacent pair from the needle and one adjacent pair from the haystack) + to determine wheter this edge from the needle is compatible with + that edge from the haystack. The default implementation always + returns true. + +bool userCheckSolution(result): + + Perform additional checks on a solution before appending it to the + results vector. When this function returns false, the solution is + ignored. The default implementation always returns true. + + +Debugging +--------- + +For debugging purposes the SubCircuit::Solver class implements a setVerbose() +method. When called once, all further calls to the solve() method cause the +algorithm to dump out a lot of debug information to stdout. + +In conjunction with setVerbose() one can also overload the userAnnotateEdge() +method in order to add additional information about the edges to the debug +output. + + +=================== +Shell Documentation +=================== + +This package also contains a small command-line tool called "scshell" that can +be used for experimentation with the algorithm. This program reads a series of +commands from stdin and reports its findings to stdout on exit. + + $ ./scshell < test_macc22.txt + + ... + + Match #3: (macc22 in macc4x2) + add_1 -> add_2 A:B B:A Y:Y + mul_1 -> mul_4 A:A B:B Y:Y + mul_2 -> mul_3 A:A B:B Y:Y + +The following commands can be used in scshell to specify graphs: + + graph + ... + endgraph + + Used to specify a graph with the given name. Only the commands + "node", "connect" and "extern" may be used within the graph ... + endgraph block. + + node [ [ []]]+ + + Used to create a node and ports. This command is a direct frontend + to the Graph::createNode() and Graph::createPort() methods. + + connect + connect + connect + + Used to connect the nodes in the graph via Graph::createConnection(). + + constant [] + + Call Graph::createConstant(). + + extern [ []]+ + + Mark signals as extern via Graph::markExtern(). + + allextern + + Mark all signals as extern via Graph::markAllExtern(). + +The following commands can be used in scshell outside a graph ... endgraph block: + + compatible + + Call Solver::addCompatibleTypes(). + + constcompat + + Call Solver::addCompatibleConstants(). + + swapgroup + + + Call Solver::addSwappablePorts(). + + swapperm + : + + + Call Solver::addSwappablePortsPermutation(). Both port lists must + have the same length and the second one must be a permutation of the + first one. + + initmap + + + Add an entry to the initial mappings for the next solve command. + This mappings are automatically reset after the solve command. + + solve [ []] + + Call Solver::solve(). The must be "1" or "true" + for true and "0" or "false" for false. + + expect + + Print all results so far since the last call to expect. Expect + results and exit with error code 1 if a different number + of results have been found. + + clearoverlap + + Call Solver::clearOverlapHistory(). + + clearconfig + + Call Solver::clearConfig(). + + verbose + + Call Solver::setVerbose(). + diff --git a/libs/subcircuit/demo.cc b/libs/subcircuit/demo.cc new file mode 100644 index 00000000..149dc6aa --- /dev/null +++ b/libs/subcircuit/demo.cc @@ -0,0 +1,134 @@ +#include "subcircuit.h" +#include + +#define VERBOSE + +int main() +{ + SubCircuit::Graph needle, haystack; + + // create needle graph + + needle.createNode("mul_1", "product"); + needle.createPort("mul_1", "A", 4); + needle.createPort("mul_1", "B", 4); + needle.createPort("mul_1", "Y", 4); + needle.markExtern("mul_1", "A"); + needle.markExtern("mul_1", "B"); + + needle.createNode("mul_2", "product"); + needle.createPort("mul_2", "A", 4); + needle.createPort("mul_2", "B", 4); + needle.createPort("mul_2", "Y", 4); + needle.markExtern("mul_2", "A"); + needle.markExtern("mul_2", "B"); + + needle.createNode("add_1", "sum"); + needle.createPort("add_1", "A", 4); + needle.createPort("add_1", "B", 4); + needle.createPort("add_1", "Y", 4); + needle.markExtern("add_1", "Y"); + + needle.createConnection("mul_1", "Y", "add_1", "A"); + needle.createConnection("mul_2", "Y", "add_1", "B"); + +#ifdef VERBOSE + printf("\n"); + needle.print(); +#endif + + // create haystack graph + +#if 0 + for (int i = 0; i < 4; i++) { + char id[100]; + snprintf(id, 100, "mul_%d", i); + haystack.createNode(id, "mul"); + haystack.createPort(id, "A", 4); + haystack.createPort(id, "B", 4); + haystack.createPort(id, "Y", 4); + haystack.markExtern(id, "A"); + haystack.markExtern(id, "B"); + } + + for (int i = 0; i < 3; i++) { + char id[100]; + snprintf(id, 100, "add_%d", i); + haystack.createNode(id, "add"); + haystack.createPort(id, "A", 4); + haystack.createPort(id, "B", 4); + haystack.createPort(id, "Y", 4); + } + + haystack.createConnection("mul_0", "Y", "add_0", "A"); + haystack.createConnection("mul_1", "Y", "add_0", "B"); + + haystack.createConnection("mul_2", "Y", "add_1", "A"); + haystack.createConnection("mul_3", "Y", "add_1", "B"); + + haystack.createConnection("add_0", "Y", "add_2", "A"); + haystack.createConnection("add_1", "Y", "add_2", "B"); + haystack.markExtern("add_2", "Y"); +#else + std::vector cellIds; + srand48(12345); + + for (int i = 0; i < 45; i++) { + char id[100]; + snprintf(id, 100, "cell_%02d", i); + haystack.createNode(id, i < 30 ? "mul" : "add"); + haystack.createPort(id, "A", 4); + haystack.createPort(id, "B", 4); + haystack.createPort(id, "Y", 4); + cellIds.push_back(id); + } + + for (int i = 0; i < int(cellIds.size()); i++) { + if (lrand48() % (i < 20 ? 3 : 2) != 0) + continue; + const std::string &id = cellIds[i]; + const std::string &id_left = cellIds[lrand48() % cellIds.size()]; + const std::string &id_right = cellIds[lrand48() % cellIds.size()]; + haystack.createConnection(id_left, "Y", id, "A"); + haystack.createConnection(id_right, "Y", id, "B"); + } +#endif + +#ifdef VERBOSE + printf("\n"); + haystack.print(); +#endif + + // search needle in haystack + + SubCircuit::Solver solver; + std::vector results; + +#ifdef VERBOSE + solver.setVerbose(); +#endif + + solver.addCompatibleTypes("product", "mul"); + solver.addCompatibleTypes("sum", "add"); + + solver.addSwappablePorts("product", "A", "B"); + solver.addSwappablePorts("sum", "A", "B"); + + solver.addGraph("needle", needle); + solver.addGraph("haystack", haystack); + solver.solve(results, "needle", "haystack"); + + for (int i = 0; i < int(results.size()); i++) { + printf("\nMatch #%d: (%s in %s)\n", i, results[i].needleGraphId.c_str(), results[i].haystackGraphId.c_str()); + for (const auto &it : results[i].mappings) { + printf(" %s -> %s", it.first.c_str(), it.second.haystackNodeId.c_str()); + for (const auto &it2 : it.second.portMapping) + printf(" %s:%s", it2.first.c_str(), it2.second.c_str()); + printf("\n"); + } + } + + printf("\n"); + return 0; +} + diff --git a/libs/subcircuit/scshell.cc b/libs/subcircuit/scshell.cc new file mode 100644 index 00000000..70afcfd4 --- /dev/null +++ b/libs/subcircuit/scshell.cc @@ -0,0 +1,235 @@ +#include "subcircuit.h" +#include +#include +#include + +std::vector readLine() +{ + char buffer[4096]; + std::vector tokenList; + + while (tokenList.size() == 0 && fgets(buffer, sizeof(buffer), stdin) != NULL) { + for (char *p = buffer; char *tok = strtok(p, " \t\r\n"); p = NULL) { + if (p != NULL && tok[0] == '#') + break; + tokenList.push_back(tok); + } + } + + return tokenList; +} + +int main() +{ + std::string graphId; + SubCircuit::Graph *graph = NULL; + SubCircuit::Solver solver; + std::map> initialMappings; + std::vector results; + std::vector cmdBuffer; + bool lastCommandExpect = false; + + while (1) + { + cmdBuffer = readLine(); + if (cmdBuffer.empty()) + break; + + printf(graph == NULL || cmdBuffer[0] == "endgraph" ? ">" : "> "); + for (const auto &tok : cmdBuffer) + printf(" %s", tok.c_str()); + printf("\n"); + + lastCommandExpect = false; + + if (graph != NULL) + { + if (cmdBuffer[0] == "node" && cmdBuffer.size() >= 3) { + graph->createNode(cmdBuffer[1], cmdBuffer[2]); + for (int i = 3; i < int(cmdBuffer.size()); i++) { + std::string portId = cmdBuffer[i]; + int width = 1, minWidth = -1; + if (i+1 < int(cmdBuffer.size()) && '0' <= cmdBuffer[i+1][0] && cmdBuffer[i+1][0] <= '9') + width = atoi(cmdBuffer[++i].c_str()); + if (i+1 < int(cmdBuffer.size()) && '0' <= cmdBuffer[i+1][0] && cmdBuffer[i+1][0] <= '9') + minWidth = atoi(cmdBuffer[++i].c_str()); + graph->createPort(cmdBuffer[1], portId, width, minWidth); + } + continue; + } + + if (cmdBuffer[0] == "connect" && cmdBuffer.size() == 5) { + graph->createConnection(cmdBuffer[1], cmdBuffer[2], cmdBuffer[3], cmdBuffer[4]); + continue; + } + + if (cmdBuffer[0] == "connect" && cmdBuffer.size() == 7) { + graph->createConnection(cmdBuffer[1], cmdBuffer[2], atoi(cmdBuffer[3].c_str()), cmdBuffer[4], cmdBuffer[5], atoi(cmdBuffer[6].c_str())); + continue; + } + + if (cmdBuffer[0] == "connect" && cmdBuffer.size() == 8) { + graph->createConnection(cmdBuffer[1], cmdBuffer[2], atoi(cmdBuffer[3].c_str()), cmdBuffer[4], cmdBuffer[5], atoi(cmdBuffer[6].c_str()), atoi(cmdBuffer[7].c_str())); + continue; + } + + if (cmdBuffer[0] == "constant" && cmdBuffer.size() == 5) { + int constValue = cmdBuffer[4].size() > 1 && cmdBuffer[4][0] == '#' ? atoi(cmdBuffer[4].c_str()+1) : cmdBuffer[4][0]; + graph->createConstant(cmdBuffer[1], cmdBuffer[2], atoi(cmdBuffer[3].c_str()), constValue); + continue; + } + + if (cmdBuffer[0] == "constant" && cmdBuffer.size() == 4) { + graph->createConstant(cmdBuffer[1], cmdBuffer[2], atoi(cmdBuffer[3].c_str())); + continue; + } + + if (cmdBuffer[0] == "extern" && cmdBuffer.size() >= 3) { + for (int i = 2; i < int(cmdBuffer.size()); i++) { + std::string portId = cmdBuffer[i]; + int bit = -1; + if (i+1 < int(cmdBuffer.size()) && '0' <= cmdBuffer[i+1][0] && cmdBuffer[i+1][0] <= '9') + bit = atoi(cmdBuffer[++i].c_str()); + graph->markExtern(cmdBuffer[1], portId, bit); + } + continue; + } + + if (cmdBuffer[0] == "allextern" && cmdBuffer.size() == 1) { + graph->markAllExtern(); + continue; + } + + if (cmdBuffer[0] == "endgraph" && cmdBuffer.size() == 1) { + solver.addGraph(graphId, *graph); + delete graph; + graph = NULL; + continue; + } + } + else + { + if (cmdBuffer[0] == "graph" && cmdBuffer.size() == 2) { + graph = new SubCircuit::Graph; + graphId = cmdBuffer[1]; + continue; + } + + if (cmdBuffer[0] == "compatible" && cmdBuffer.size() == 3) { + solver.addCompatibleTypes(cmdBuffer[1], cmdBuffer[2]); + continue; + } + + if (cmdBuffer[0] == "constcompat" && cmdBuffer.size() == 3) { + int needleConstValue = cmdBuffer[1].size() > 1 && cmdBuffer[1][0] == '#' ? atoi(cmdBuffer[1].c_str()+1) : cmdBuffer[1][0]; + int haystackConstValue = cmdBuffer[2].size() > 1 && cmdBuffer[2][0] == '#' ? atoi(cmdBuffer[2].c_str()+1) : cmdBuffer[2][0]; + solver.addCompatibleConstants(needleConstValue, haystackConstValue); + continue; + } + + if (cmdBuffer[0] == "swapgroup" && cmdBuffer.size() >= 4) { + std::set ports; + for (int i = 2; i < int(cmdBuffer.size()); i++) + ports.insert(cmdBuffer[i]); + solver.addSwappablePorts(cmdBuffer[1], ports); + continue; + } + + if (cmdBuffer[0] == "swapperm" && cmdBuffer.size() >= 4 && cmdBuffer.size() % 2 == 1 && cmdBuffer[cmdBuffer.size()/2 + 1] == ":") { + std::map portMapping; + int n = (cmdBuffer.size()-3) / 2; + for (int i = 0; i < n; i++) + portMapping[cmdBuffer[i+2]] = cmdBuffer[i+3+n]; + solver.addSwappablePortsPermutation(cmdBuffer[1], portMapping); + continue; + } + + if (cmdBuffer[0] == "initmap" && cmdBuffer.size() >= 4) { + for (int i = 2; i < int(cmdBuffer.size()); i++) + initialMappings[cmdBuffer[1]].insert(cmdBuffer[i]); + continue; + } + + if (cmdBuffer[0] == "solve" && 3 <= cmdBuffer.size() && cmdBuffer.size() <= 5) { + bool allowOverlap = true; + int maxSolutions = -1; + if (cmdBuffer.size() >= 4) + allowOverlap = cmdBuffer[3] == "true" || atoi(cmdBuffer[3].c_str()) ? true : false; + if (cmdBuffer.size() >= 5) + maxSolutions = atoi(cmdBuffer[4].c_str()); + solver.solve(results, cmdBuffer[1], cmdBuffer[2], initialMappings, allowOverlap, maxSolutions); + initialMappings.clear(); + continue; + } + + if (cmdBuffer[0] == "clearoverlap" && cmdBuffer.size() == 1) { + solver.clearOverlapHistory(); + continue; + } + + if (cmdBuffer[0] == "clearconfig" && cmdBuffer.size() == 1) { + solver.clearConfig(); + continue; + } + + if (cmdBuffer[0] == "verbose" && cmdBuffer.size() == 1) { + solver.setVerbose(); + continue; + } + + if (cmdBuffer[0] == "expect" && cmdBuffer.size() == 2) { + int expected = atoi(cmdBuffer[1].c_str()); + printf("\n-- Expected %d, Got %d --\n", expected, int(results.size())); + for (int i = 0; i < int(results.size()); i++) { + printf("\nMatch #%d: (%s in %s)\n", i, results[i].needleGraphId.c_str(), results[i].haystackGraphId.c_str()); + for (const auto &it : results[i].mappings) { + printf(" %s -> %s", it.first.c_str(), it.second.haystackNodeId.c_str()); + for (const auto &it2 : it.second.portMapping) + printf(" %s:%s", it2.first.c_str(), it2.second.c_str()); + printf("\n"); + } + } + printf("\n"); + if (expected != int(results.size())) { + printf("^^ expected %d, Got %d ^^\n\n", expected, int(results.size())); + printf(" +----------------+\n"); + printf(" | \\|/ ____ \\|/ |\n"); + printf(" | \"@'/ ,. \\`@\" |\n"); + printf(" | /_| \\__/ |_\\ |\n"); + printf(" | \\__U_/ |\n"); + printf(" | | | |\n"); + printf(" +----------------+\n\n"); + return 1; + } + results.clear(); + lastCommandExpect = true; + continue; + } + } + + printf("Invalid input command!\n"); + return 1; + } + + if (graph) + delete graph; + + if (!lastCommandExpect) { + printf("\n-- Got %d --\n", int(results.size())); + for (int i = 0; i < int(results.size()); i++) { + printf("\nMatch #%d: (%s in %s)\n", i, results[i].needleGraphId.c_str(), results[i].haystackGraphId.c_str()); + for (const auto &it : results[i].mappings) { + printf(" %s -> %s", it.first.c_str(), it.second.haystackNodeId.c_str()); + for (const auto &it2 : it.second.portMapping) + printf(" %s:%s", it2.first.c_str(), it2.second.c_str()); + printf("\n"); + } + } + } else + printf("PASSED.\n"); + + printf("\n"); + + return 0; +} + diff --git a/libs/subcircuit/subcircuit.cc b/libs/subcircuit/subcircuit.cc new file mode 100644 index 00000000..b49fa97c --- /dev/null +++ b/libs/subcircuit/subcircuit.cc @@ -0,0 +1,1264 @@ +/* + * SubCircuit -- An implementation of the Ullmann Subgraph Isomorphism + * algorithm for coarse grain logic networks + * + * Copyright (C) 2013 Clifford Wolf + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "subcircuit.h" + +#include +#include +#include +#include + +using namespace SubCircuit; + +static std::string stringf(const char *fmt, ...) +{ + std::string string; + char *str = NULL; + va_list ap; + + va_start(ap, fmt); + if (vasprintf(&str, fmt, ap) < 0) + str = NULL; + va_end(ap); + + if (str != NULL) { + string = str; + free(str); + } + + return string; +} + +bool SubCircuit::Graph::BitRef::operator < (const BitRef &other) const +{ + if (nodeIdx != other.nodeIdx) + return nodeIdx < other.nodeIdx; + if (portIdx != other.portIdx) + return portIdx < other.portIdx; + return bitIdx < other.bitIdx; +} + +void SubCircuit::Graph::createNode(std::string nodeId, std::string typeId, void *userData) +{ + assert(nodeMap.count(nodeId) == 0); + nodeMap[nodeId] = nodes.size(); + nodes.push_back(Node()); + + Node &newNode = nodes.back(); + newNode.nodeId = nodeId; + newNode.typeId = typeId; + newNode.userData = userData; +} + +void SubCircuit::Graph::createPort(std::string nodeId, std::string portId, int width, int minWidth) +{ + assert(nodeMap.count(nodeId) != 0); + int nodeIdx = nodeMap[nodeId]; + Node &node = nodes[nodeIdx]; + + assert(node.portMap.count(portId) == 0); + + int portIdx = node.ports.size(); + node.portMap[portId] = portIdx; + node.ports.push_back(Port()); + Port &port = node.ports.back(); + + port.portId = portId; + port.minWidth = minWidth < 0 ? width : minWidth; + port.bits.insert(port.bits.end(), width, PortBit()); + + for (int i = 0; i < width; i++) { + port.bits[i].edgeIdx = edges.size(); + edges.push_back(Edge()); + edges.back().portBits.insert(BitRef(nodeIdx, portIdx, i)); + } +} + +void SubCircuit::Graph::createConnection(std::string fromNodeId, std::string fromPortId, int fromBit, std::string toNodeId, std::string toPortId, int toBit, int width) +{ + assert(nodeMap.count(fromNodeId) != 0); + assert(nodeMap.count(toNodeId) != 0); + + int fromNodeIdx = nodeMap[fromNodeId]; + Node &fromNode = nodes[fromNodeIdx]; + + int toNodeIdx = nodeMap[toNodeId]; + Node &toNode = nodes[toNodeIdx]; + + assert(fromNode.portMap.count(fromPortId) != 0); + assert(toNode.portMap.count(toPortId) != 0); + + int fromPortIdx = fromNode.portMap[fromPortId]; + Port &fromPort = fromNode.ports[fromPortIdx]; + + int toPortIdx = toNode.portMap[toPortId]; + Port &toPort = toNode.ports[toPortIdx]; + + if (width < 0) { + assert(fromBit == 0 && toBit == 0); + assert(fromPort.bits.size() == toPort.bits.size()); + width = fromPort.bits.size(); + } + + assert(fromBit >= 0 && toBit >= 0); + for (int i = 0; i < width; i++) + { + assert(fromBit + i < int(fromPort.bits.size())); + assert(toBit + i < int(toPort.bits.size())); + + int fromEdgeIdx = fromPort.bits[fromBit + i].edgeIdx; + int toEdgeIdx = toPort.bits[toBit + i].edgeIdx; + + if (fromEdgeIdx == toEdgeIdx) + continue; + + // merge toEdge into fromEdge + if (edges[toEdgeIdx].isExtern) + edges[fromEdgeIdx].isExtern = true; + if (edges[toEdgeIdx].constValue) { + assert(edges[fromEdgeIdx].constValue == 0); + edges[fromEdgeIdx].constValue = edges[toEdgeIdx].constValue; + } + for (const auto &ref : edges[toEdgeIdx].portBits) { + edges[fromEdgeIdx].portBits.insert(ref); + nodes[ref.nodeIdx].ports[ref.portIdx].bits[ref.bitIdx].edgeIdx = fromEdgeIdx; + } + + // remove toEdge (move last edge over toEdge if needed) + if (toEdgeIdx+1 != int(edges.size())) { + edges[toEdgeIdx] = edges.back(); + for (const auto &ref : edges[toEdgeIdx].portBits) + nodes[ref.nodeIdx].ports[ref.portIdx].bits[ref.bitIdx].edgeIdx = toEdgeIdx; + } + edges.pop_back(); + } +} + +void SubCircuit::Graph::createConnection(std::string fromNodeId, std::string fromPortId, std::string toNodeId, std::string toPortId) +{ + createConnection(fromNodeId, fromPortId, 0, toNodeId, toPortId, 0, -1); +} + +void SubCircuit::Graph::createConstant(std::string toNodeId, std::string toPortId, int toBit, int constValue) +{ + assert(nodeMap.count(toNodeId) != 0); + int toNodeIdx = nodeMap[toNodeId]; + Node &toNode = nodes[toNodeIdx]; + + assert(toNode.portMap.count(toPortId) != 0); + int toPortIdx = toNode.portMap[toPortId]; + Port &toPort = toNode.ports[toPortIdx]; + + assert(toBit >= 0 && toBit < int(toPort.bits.size())); + int toEdgeIdx = toPort.bits[toBit].edgeIdx; + + assert(edges[toEdgeIdx].constValue == 0); + edges[toEdgeIdx].constValue = constValue; +} + +void SubCircuit::Graph::createConstant(std::string toNodeId, std::string toPortId, int constValue) +{ + assert(nodeMap.count(toNodeId) != 0); + int toNodeIdx = nodeMap[toNodeId]; + Node &toNode = nodes[toNodeIdx]; + + assert(toNode.portMap.count(toPortId) != 0); + int toPortIdx = toNode.portMap[toPortId]; + Port &toPort = toNode.ports[toPortIdx]; + + for (int i = 0; i < int(toPort.bits.size()); i++) { + int toEdgeIdx = toPort.bits[i].edgeIdx; + assert(edges[toEdgeIdx].constValue == 0); + edges[toEdgeIdx].constValue = constValue % 2 ? '1' : '0'; + constValue = constValue >> 1; + } +} + +void SubCircuit::Graph::markExtern(std::string nodeId, std::string portId, int bit) +{ + assert(nodeMap.count(nodeId) != 0); + Node &node = nodes[nodeMap[nodeId]]; + + assert(node.portMap.count(portId) != 0); + Port &port = node.ports[node.portMap[portId]]; + + if (bit < 0) { + for (const auto portBit : port.bits) + edges[portBit.edgeIdx].isExtern = true; + } else { + assert(bit < int(port.bits.size())); + edges[port.bits[bit].edgeIdx].isExtern = true; + } +} + +void SubCircuit::Graph::markAllExtern() +{ + allExtern = true; +} + +void SubCircuit::Graph::print() +{ + for (int i = 0; i < int(nodes.size()); i++) { + const Node &node = nodes[i]; + printf("NODE %d: %s (%s)\n", i, node.nodeId.c_str(), node.typeId.c_str()); + for (int j = 0; j < int(node.ports.size()); j++) { + const Port &port = node.ports[j]; + printf(" PORT %d: %s (%d/%d)\n", j, port.portId.c_str(), port.minWidth, int(port.bits.size())); + for (int k = 0; k < int(port.bits.size()); k++) { + int edgeIdx = port.bits[k].edgeIdx; + printf(" BIT %d (%d):", k, edgeIdx); + for (const auto &ref : edges[edgeIdx].portBits) + printf(" %d.%d.%d", ref.nodeIdx, ref.portIdx, ref.bitIdx); + if (edges[edgeIdx].isExtern) + printf(" [extern]"); + printf("\n"); + } + } + } +} + +class SubCircuit::SolverWorker +{ + // basic internal data structures + + typedef std::vector> adjMatrix_t; + + struct GraphData { + std::string graphId; + Graph graph; + adjMatrix_t adjMatrix; + std::vector usedNodes; + }; + + static void printAdjMatrix(const adjMatrix_t &matrix) + { + printf("%7s", ""); + for (int i = 0; i < int(matrix.size()); i++) + printf("%4d:", i); + printf("\n"); + for (int i = 0; i < int(matrix.size()); i++) { + printf("%5d:", i); + for (int j = 0; j < int(matrix.size()); j++) + if (matrix.at(i).count(j) == 0) + printf("%5s", "-"); + else + printf("%5d", matrix.at(i).at(j)); + printf("\n"); + } + } + + // helper functions for handling permutations + + static const int maxPermutationsLimit = 1000000; + + static int numberOfPermutations(const std::vector &list) + { + int numPermutations = 1; + for (int i = 0; i < int(list.size()); i++) { + assert(numPermutations < maxPermutationsLimit); + numPermutations *= i+1; + } + return numPermutations; + } + + static void permutateVectorToMap(std::map &map, const std::vector &list, int idx) + { + // convert idx to a list.size() digits factoradic number + + std::vector factoradicDigits; + for (int i = 0; i < int(list.size()); i++) { + factoradicDigits.push_back(idx % (i+1)); + idx = idx / (i+1); + } + + // construct permutation + + std::vector pool = list; + std::vector permutation; + + while (!factoradicDigits.empty()) { + int i = factoradicDigits.back(); + factoradicDigits.pop_back(); + permutation.push_back(pool[i]); + pool.erase(pool.begin() + i); + } + + // update map + + for (int i = 0; i < int(list.size()); i++) + map[list[i]] = permutation[i]; + } + + static int numberOfPermutationsArray(const std::vector> &list) + { + int numPermutations = 1; + for (const auto &it : list) { + int thisPermutations = numberOfPermutations(it); + assert(float(numPermutations) * float(thisPermutations) < maxPermutationsLimit); + numPermutations *= thisPermutations; + } + return numPermutations; + } + + static void permutateVectorToMapArray(std::map &map, const std::vector> &list, int idx) + { + for (const auto &it : list) { + int thisPermutations = numberOfPermutations(it); + int thisIdx = idx % thisPermutations; + permutateVectorToMap(map, it, thisIdx); + idx /= thisPermutations; + } + } + + static void applyPermutation(std::map &map, const std::map &permutation) + { + std::vector> changeLog; + for (const auto &it : permutation) + if (map.count(it.second)) + changeLog.push_back(std::pair(it.first, map.at(it.second))); + else + changeLog.push_back(std::pair(it.first, it.second)); + for (const auto &it : changeLog) + map[it.first] = it.second; + } + + // classes for internal digraph representation + + struct DiBit + { + std::string fromPort, toPort; + int fromBit, toBit; + + DiBit() : fromPort(), toPort(), fromBit(-1), toBit(-1) { } + DiBit(std::string fromPort, int fromBit, std::string toPort, int toBit) : fromPort(fromPort), toPort(toPort), fromBit(fromBit), toBit(toBit) { } + + bool operator < (const DiBit &other) const + { + if (fromPort != other.fromPort) + return fromPort < other.fromPort; + if (toPort != other.toPort) + return toPort < other.toPort; + if (fromBit != other.fromBit) + return fromBit < other.fromBit; + return toBit < other.toBit; + } + + std::string toString() const + { + return stringf("%s[%d]:%s[%d]", fromPort.c_str(), fromBit, toPort.c_str(), toBit); + } + }; + + struct DiNode + { + std::string typeId; + std::map portSizes; + + DiNode() + { + } + + DiNode(const Graph &graph, int nodeIdx) + { + const Graph::Node &node = graph.nodes.at(nodeIdx); + typeId = node.typeId; + for (const auto &port : node.ports) + portSizes[port.portId] = port.bits.size(); + } + + bool operator < (const DiNode &other) const + { + if (typeId != other.typeId) + return typeId < other.typeId; + return portSizes < other.portSizes; + } + + std::string toString() const + { + std::string str; + bool firstPort = true; + for (const auto &it : portSizes) { + str += stringf("%s%s[%d]", firstPort ? "" : ",", it.first.c_str(), it.second); + firstPort = false; + } + return typeId + "(" + str + ")"; + } + }; + + struct DiEdge + { + DiNode fromNode, toNode; + std::set bits; + std::string userAnnotation; + + bool operator < (const DiEdge &other) const + { + if (fromNode < other.fromNode || other.fromNode < fromNode) + return fromNode < other.fromNode; + if (toNode < other.toNode || other.toNode < toNode) + return toNode < other.toNode; + if (bits < other.bits || other.bits < bits) + return bits < other.bits; + return userAnnotation < other.userAnnotation; + } + + bool compare(const DiEdge &other, const std::map &mapFromPorts, const std::map &mapToPorts) const + { + // Rules for matching edges: + // + // For all bits in the needle edge: + // - ignore if needle ports don't exist in haystack edge + // - otherwise: matching bit in haystack edge must exist + // + // There is no need to check in the other direction, as checking + // of the isExtern properties is already performed in node matching. + // + // Note: "this" is needle, "other" is haystack + + for (auto bit : bits) + { + if (mapFromPorts.count(bit.fromPort) > 0) + bit.fromPort = mapFromPorts.at(bit.fromPort); + if (mapToPorts.count(bit.toPort) > 0) + bit.toPort = mapToPorts.at(bit.toPort); + + if (other.fromNode.portSizes.count(bit.fromPort) == 0) + continue; + if (other.toNode.portSizes.count(bit.toPort) == 0) + continue; + + if (bit.fromBit >= other.fromNode.portSizes.at(bit.fromPort)) + continue; + if (bit.toBit >= other.toNode.portSizes.at(bit.toPort)) + continue; + + if (other.bits.count(bit) == 0) + return false; + } + + return true; + } + + bool compareWithFromAndToPermutations(const DiEdge &other, const std::map &mapFromPorts, const std::map &mapToPorts, + const std::map>> &swapPermutations) const + { + if (swapPermutations.count(fromNode.typeId) > 0) + for (const auto &permutation : swapPermutations.at(fromNode.typeId)) { + std::map thisMapFromPorts = mapFromPorts; + applyPermutation(thisMapFromPorts, permutation); + if (compareWithToPermutations(other, thisMapFromPorts, mapToPorts, swapPermutations)) + return true; + } + return compareWithToPermutations(other, mapFromPorts, mapToPorts, swapPermutations); + } + + bool compareWithToPermutations(const DiEdge &other, const std::map &mapFromPorts, const std::map &mapToPorts, + const std::map>> &swapPermutations) const + { + if (swapPermutations.count(toNode.typeId) > 0) + for (const auto &permutation : swapPermutations.at(toNode.typeId)) { + std::map thisMapToPorts = mapToPorts; + applyPermutation(thisMapToPorts, permutation); + if (compare(other, mapFromPorts, thisMapToPorts)) + return true; + } + return compare(other, mapFromPorts, mapToPorts); + } + + bool compare(const DiEdge &other, const std::map>> &swapPorts, + const std::map>> &swapPermutations) const + { + // brute force method for port swapping: try all variations + + std::vector> swapFromPorts; + std::vector> swapToPorts; + + // only use groups that are relevant for this edge + + if (swapPorts.count(fromNode.typeId) > 0) + for (const auto &ports : swapPorts.at(fromNode.typeId)) { + for (const auto &bit : bits) + if (ports.count(bit.fromPort)) + goto foundFromPortMatch; + if (0) { + foundFromPortMatch: + std::vector portsVector; + for (const auto &port : ports) + portsVector.push_back(port); + swapFromPorts.push_back(portsVector); + } + } + + if (swapPorts.count(toNode.typeId) > 0) + for (const auto &ports : swapPorts.at(toNode.typeId)) { + for (const auto &bit : bits) + if (ports.count(bit.toPort)) + goto foundToPortMatch; + if (0) { + foundToPortMatch: + std::vector portsVector; + for (const auto &port : ports) + portsVector.push_back(port); + swapToPorts.push_back(portsVector); + } + } + + // try all permutations + + std::map mapFromPorts, mapToPorts; + int fromPortsPermutations = numberOfPermutationsArray(swapFromPorts); + int toPortsPermutations = numberOfPermutationsArray(swapToPorts); + + for (int i = 0; i < fromPortsPermutations; i++) + { + permutateVectorToMapArray(mapFromPorts, swapFromPorts, i); + + for (int j = 0; j < toPortsPermutations; j++) { + permutateVectorToMapArray(mapToPorts, swapToPorts, j); + if (compareWithFromAndToPermutations(other, mapFromPorts, mapToPorts, swapPermutations)) + return true; + } + } + + return false; + } + + bool compare(const DiEdge &other, const std::map &mapFromPorts, const std::map>> &swapPorts, + const std::map>> &swapPermutations) const + { + // strip-down version of the last function: only try permutations for mapToPorts, mapFromPorts is already provided by the caller + + std::vector> swapToPorts; + + if (swapPorts.count(toNode.typeId) > 0) + for (const auto &ports : swapPorts.at(toNode.typeId)) { + for (const auto &bit : bits) + if (ports.count(bit.toPort)) + goto foundToPortMatch; + if (0) { + foundToPortMatch: + std::vector portsVector; + for (const auto &port : ports) + portsVector.push_back(port); + swapToPorts.push_back(portsVector); + } + } + + std::map mapToPorts; + int toPortsPermutations = numberOfPermutationsArray(swapToPorts); + + for (int j = 0; j < toPortsPermutations; j++) { + permutateVectorToMapArray(mapToPorts, swapToPorts, j); + if (compareWithToPermutations(other, mapFromPorts, mapToPorts, swapPermutations)) + return true; + } + + return false; + } + + std::string toString() const + { + std::string buffer = fromNode.toString() + " " + toNode.toString(); + for (const auto &bit : bits) + buffer += " " + bit.toString(); + if (!userAnnotation.empty()) + buffer += " " + userAnnotation; + return buffer; + } + + static void findEdgesInGraph(const Graph &graph, std::map, DiEdge> &edges) + { + edges.clear(); + for (const auto &edge : graph.edges) { + if (edge.constValue != 0) + continue; + for (const auto &fromBit : edge.portBits) + for (const auto &toBit : edge.portBits) + if (&fromBit != &toBit) { + DiEdge &de = edges[std::pair(fromBit.nodeIdx, toBit.nodeIdx)]; + de.fromNode = DiNode(graph, fromBit.nodeIdx); + de.toNode = DiNode(graph, toBit.nodeIdx); + std::string fromPortId = graph.nodes[fromBit.nodeIdx].ports[fromBit.portIdx].portId; + std::string toPortId = graph.nodes[toBit.nodeIdx].ports[toBit.portIdx].portId; + de.bits.insert(DiBit(fromPortId, fromBit.bitIdx, toPortId, toBit.bitIdx)); + } + } + } + }; + + struct DiCache + { + std::map edgeTypesMap; + std::vector edgeTypes; + std::map, bool> compareCache; + + void add(const Graph &graph, adjMatrix_t &adjMatrix, const std::string &graphId, Solver *userSolver) + { + std::map, DiEdge> edges; + DiEdge::findEdgesInGraph(graph, edges); + + adjMatrix.clear(); + adjMatrix.resize(graph.nodes.size()); + + for (auto &it : edges) { + const Graph::Node &fromNode = graph.nodes[it.first.first]; + const Graph::Node &toNode = graph.nodes[it.first.second]; + it.second.userAnnotation = userSolver->userAnnotateEdge(graphId, fromNode.nodeId, fromNode.userData, toNode.nodeId, toNode.userData); + } + + for (const auto &it : edges) { + if (edgeTypesMap.count(it.second) == 0) { + edgeTypesMap[it.second] = edgeTypes.size(); + edgeTypes.push_back(it.second); + } + adjMatrix[it.first.first][it.first.second] = edgeTypesMap[it.second]; + } + } + + bool compare(int needleEdge, int haystackEdge, const std::map>> &swapPorts, + const std::map>> &swapPermutations) + { + std::pair key(needleEdge, haystackEdge); + if (!compareCache.count(key)) + compareCache[key] = edgeTypes.at(needleEdge).compare(edgeTypes.at(haystackEdge), swapPorts, swapPermutations); + return compareCache[key]; + } + + bool compare(int needleEdge, int haystackEdge, const std::map &mapFromPorts, const std::map>> &swapPorts, + const std::map>> &swapPermutations) const + { + return edgeTypes.at(needleEdge).compare(edgeTypes.at(haystackEdge), mapFromPorts, swapPorts, swapPermutations); + } + + bool compare(int needleEdge, int haystackEdge, const std::map &mapFromPorts, const std::map &mapToPorts) const + { + return edgeTypes.at(needleEdge).compare(edgeTypes.at(haystackEdge), mapFromPorts, mapToPorts); + } + + void printEdgeTypes() const + { + for (int i = 0; i < int(edgeTypes.size()); i++) + printf("%5d: %s\n", i, edgeTypes[i].toString().c_str()); + } + }; + + // solver state variables + + Solver *userSolver; + std::map graphData; + std::map> compatibleTypes; + std::map> compatibleConstants; + std::map>> swapPorts; + std::map>> swapPermutations; + DiCache diCache; + bool verbose; + + // main solver functions + + bool matchNodes(const Graph &needle, int needleNodeIdx, const Graph &haystack, int haystackNodeIdx) const + { + // Rules for matching nodes: + // + // 1. their typeId must be identical or compatible + // (this is checked before calling this function) + // + // 2. they must have the same ports and the haystack port + // widths must match the needle port width range + // + // 3. All edges from the needle must match the haystack: + // a) if the needle edge is extern: + // - the haystack edge must have at least as many components as the needle edge + // b) if the needle edge is not extern: + // - the haystack edge must have the same number of components as the needle edge + // - the haystack edge must not be extern + + const Graph::Node &nn = needle.nodes[needleNodeIdx]; + const Graph::Node &hn = haystack.nodes[haystackNodeIdx]; + + assert(nn.typeId == hn.typeId || (compatibleTypes.count(nn.typeId) > 0 && compatibleTypes.at(nn.typeId).count(hn.typeId) > 0)); + + if (nn.ports.size() != hn.ports.size()) + return false; + + for (int i = 0; i < int(nn.ports.size()); i++) + { + if (hn.portMap.count(nn.ports[i].portId) == 0) + return false; + + const Graph::Port &np = nn.ports[i]; + const Graph::Port &hp = hn.ports[hn.portMap.at(nn.ports[i].portId)]; + + if (int(hp.bits.size()) < np.minWidth || hp.bits.size() > np.bits.size()) + return false; + + for (int j = 0; j < int(hp.bits.size()); j++) + { + const Graph::Edge &ne = needle.edges[np.bits[j].edgeIdx]; + const Graph::Edge &he = haystack.edges[hp.bits[j].edgeIdx]; + + if (ne.constValue || he.constValue) { + if (ne.constValue != he.constValue) + if (compatibleConstants.count(ne.constValue) == 0 || compatibleConstants.at(ne.constValue).count(he.constValue) == 0) + return false; + continue; + } + + if (ne.isExtern || needle.allExtern) { + if (he.portBits.size() < ne.portBits.size()) + return false; + } else { + if (he.portBits.size() != ne.portBits.size()) + return false; + if (he.isExtern || haystack.allExtern) + return false; + } + } + } + + return true; + } + + void generateEnumerationMatrix(std::vector> &enumerationMatrix, const GraphData &needle, const GraphData &haystack, const std::map> &initialMappings) const + { + std::map> haystackNodesByTypeId; + for (int i = 0; i < int(haystack.graph.nodes.size()); i++) + haystackNodesByTypeId[haystack.graph.nodes[i].typeId].insert(i); + + enumerationMatrix.clear(); + enumerationMatrix.resize(needle.graph.nodes.size()); + for (int i = 0; i < int(needle.graph.nodes.size()); i++) + { + const Graph::Node &nn = needle.graph.nodes[i]; + + for (int j : haystackNodesByTypeId[nn.typeId]) { + const Graph::Node &hn = haystack.graph.nodes[j]; + if (initialMappings.count(nn.nodeId) > 0 && initialMappings.at(nn.nodeId).count(hn.nodeId) == 0) + continue; + if (!matchNodes(needle.graph, i, haystack.graph, j)) + continue; + if (userSolver->userCompareNodes(needle.graphId, nn.nodeId, nn.userData, haystack.graphId, hn.nodeId, hn.userData)) + enumerationMatrix[i].insert(j); + } + + if (compatibleTypes.count(nn.typeId) > 0) + for (const std::string &compatibleTypeId : compatibleTypes.at(nn.typeId)) + for (int j : haystackNodesByTypeId[compatibleTypeId]) { + const Graph::Node &hn = haystack.graph.nodes[j]; + if (initialMappings.count(nn.nodeId) > 0 && initialMappings.at(nn.nodeId).count(hn.nodeId) == 0) + continue; + if (!matchNodes(needle.graph, i, haystack.graph, j)) + continue; + if (userSolver->userCompareNodes(needle.graphId, nn.nodeId, nn.userData, haystack.graphId, hn.nodeId, hn.userData)) + enumerationMatrix[i].insert(j); + } + } + } + + bool checkEnumerationMatrix(std::vector> &enumerationMatrix, int i, int j, const GraphData &needle, const GraphData &haystack) + { + for (const auto &it_needle : needle.adjMatrix.at(i)) + { + int needleNeighbour = it_needle.first; + int needleEdgeType = it_needle.second; + + for (int haystackNeighbour : enumerationMatrix[needleNeighbour]) + if (haystack.adjMatrix.at(j).count(haystackNeighbour) > 0) { + int haystackEdgeType = haystack.adjMatrix.at(j).at(haystackNeighbour); + if (diCache.compare(needleEdgeType, haystackEdgeType, swapPorts, swapPermutations)) { + const Graph::Node &needleFromNode = needle.graph.nodes[i]; + const Graph::Node &needleToNode = needle.graph.nodes[needleNeighbour]; + const Graph::Node &haystackFromNode = haystack.graph.nodes[j]; + const Graph::Node &haystackToNode = haystack.graph.nodes[haystackNeighbour]; + if (userSolver->userCompareEdge(needle.graphId, needleFromNode.nodeId, needleFromNode.userData, needleToNode.nodeId, needleToNode.userData, + haystack.graphId, haystackFromNode.nodeId, haystackFromNode.userData, haystackToNode.nodeId, haystackToNode.userData)) + goto found_match; + } + } + + return false; + found_match:; + } + + return true; + } + + bool pruneEnumerationMatrix(std::vector> &enumerationMatrix, const GraphData &needle, const GraphData &haystack, int &nextRow) + { + bool didSomething = true; + while (didSomething) + { + nextRow = -1; + didSomething = false; + for (int i = 0; i < int(enumerationMatrix.size()); i++) { + std::set newRow; + for (int j : enumerationMatrix[i]) { + if (checkEnumerationMatrix(enumerationMatrix, i, j, needle, haystack)) + newRow.insert(j); + else + didSomething = true; + } + if (newRow.size() == 0) + return false; + if (newRow.size() >= 2 && (nextRow < 0 || needle.adjMatrix.at(nextRow).size() < needle.adjMatrix.at(i).size())) + nextRow = i; + enumerationMatrix[i].swap(newRow); + } + } + return true; + } + + void printEnumerationMatrix(const std::vector> &enumerationMatrix, int maxHaystackNodeIdx = -1) const + { + if (maxHaystackNodeIdx < 0) { + for (const auto &it : enumerationMatrix) + for (int idx : it) + maxHaystackNodeIdx = std::max(maxHaystackNodeIdx, idx); + } + + printf(" "); + for (int j = 0; j < maxHaystackNodeIdx; j += 5) + printf("%-6d", j); + printf("\n"); + + for (int i = 0; i < int(enumerationMatrix.size()); i++) + { + printf("%5d:", i); + for (int j = 0; j < maxHaystackNodeIdx; j++) { + if (j % 5 == 0) + printf(" "); + printf("%c", enumerationMatrix[i].count(j) > 0 ? '*' : '.'); + } + printf("\n"); + } + } + + bool checkPortmapCandidate(const std::vector> &enumerationMatrix, const GraphData &needle, const GraphData &haystack, int idx, const std::map ¤tCandidate) + { + assert(enumerationMatrix[idx].size() == 1); + int idxHaystack = *enumerationMatrix[idx].begin(); + + for (const auto &it_needle : needle.adjMatrix.at(idx)) + { + int needleNeighbour = it_needle.first; + int needleEdgeType = it_needle.second; + + assert(enumerationMatrix[needleNeighbour].size() == 1); + int haystackNeighbour = *enumerationMatrix[needleNeighbour].begin(); + + assert(haystack.adjMatrix.at(idxHaystack).count(haystackNeighbour) > 0); + int haystackEdgeType = haystack.adjMatrix.at(idxHaystack).at(haystackNeighbour); + if (!diCache.compare(needleEdgeType, haystackEdgeType, currentCandidate, swapPorts, swapPermutations)) + return false; + } + return true; + } + + void generatePortmapCandidates(std::set> &portmapCandidates, const std::vector> &enumerationMatrix, + const GraphData &needle, const GraphData &haystack, int idx) + { + std::map currentCandidate; + + for (const auto &port : needle.graph.nodes[idx].ports) + currentCandidate[port.portId] = port.portId; + + if (swapPorts.count(needle.graph.nodes[idx].typeId) == 0) + { + if (checkPortmapCandidate(enumerationMatrix, needle, haystack, idx, currentCandidate)) + portmapCandidates.insert(currentCandidate); + + if (swapPermutations.count(needle.graph.nodes[idx].typeId) > 0) + for (const auto &permutation : swapPermutations.at(needle.graph.nodes[idx].typeId)) { + std::map currentSubCandidate = currentCandidate; + applyPermutation(currentSubCandidate, permutation); + if (checkPortmapCandidate(enumerationMatrix, needle, haystack, idx, currentSubCandidate)) + portmapCandidates.insert(currentSubCandidate); + } + } + else + { + std::vector> thisSwapPorts; + for (const auto &ports : swapPorts.at(needle.graph.nodes[idx].typeId)) { + std::vector portsVector; + for (const auto &port : ports) + portsVector.push_back(port); + thisSwapPorts.push_back(portsVector); + } + + int thisPermutations = numberOfPermutationsArray(thisSwapPorts); + for (int i = 0; i < thisPermutations; i++) + { + permutateVectorToMapArray(currentCandidate, thisSwapPorts, i); + + if (checkPortmapCandidate(enumerationMatrix, needle, haystack, idx, currentCandidate)) + portmapCandidates.insert(currentCandidate); + + if (swapPermutations.count(needle.graph.nodes[idx].typeId) > 0) + for (const auto &permutation : swapPermutations.at(needle.graph.nodes[idx].typeId)) { + std::map currentSubCandidate = currentCandidate; + applyPermutation(currentSubCandidate, permutation); + if (checkPortmapCandidate(enumerationMatrix, needle, haystack, idx, currentSubCandidate)) + portmapCandidates.insert(currentSubCandidate); + } + } + } + } + + bool prunePortmapCandidates(std::vector>> &portmapCandidates, std::vector> enumerationMatrix, const GraphData &needle, const GraphData &haystack) + { + bool didSomething = false; + + // strategy #1: prune impossible port mappings + + for (int i = 0; i < int(needle.graph.nodes.size()); i++) + { + assert(enumerationMatrix[i].size() == 1); + int j = *enumerationMatrix[i].begin(); + + std::set> thisCandidates; + portmapCandidates[i].swap(thisCandidates); + + for (const auto &testCandidate : thisCandidates) + { + for (const auto &it_needle : needle.adjMatrix.at(i)) + { + int needleNeighbour = it_needle.first; + int needleEdgeType = it_needle.second; + + assert(enumerationMatrix[needleNeighbour].size() == 1); + int haystackNeighbour = *enumerationMatrix[needleNeighbour].begin(); + + assert(haystack.adjMatrix.at(j).count(haystackNeighbour) > 0); + int haystackEdgeType = haystack.adjMatrix.at(j).at(haystackNeighbour); + + for (const auto &otherCandidate : portmapCandidates[needleNeighbour]) { + if (diCache.compare(needleEdgeType, haystackEdgeType, testCandidate, otherCandidate)) + goto found_match; + } + + didSomething = true; + goto purgeCandidate; + found_match:; + } + + portmapCandidates[i].insert(testCandidate); + purgeCandidate:; + } + + if (portmapCandidates[i].size() == 0) + return false; + } + + if (didSomething) + return true; + + // strategy #2: prune a single random port mapping + + for (int i = 0; i < int(needle.graph.nodes.size()); i++) + if (portmapCandidates[i].size() > 1) { + // remove last mapping. this keeps ports unswapped in don't-care situations + portmapCandidates[i].erase(--portmapCandidates[i].end()); + return true; + } + + return false; + } + + void ullmannRecursion(std::vector &results, std::vector> &enumerationMatrix, int iter, const GraphData &needle, GraphData &haystack, bool allowOverlap, int limitResults) + { + int i = -1; + if (!pruneEnumerationMatrix(enumerationMatrix, needle, haystack, i)) + return; + + if (i < 0) + { + Solver::Result result; + result.needleGraphId = needle.graphId; + result.haystackGraphId = haystack.graphId; + + std::vector>> portmapCandidates; + portmapCandidates.resize(enumerationMatrix.size()); + + for (int j = 0; j < int(enumerationMatrix.size()); j++) { + Solver::ResultNodeMapping mapping; + mapping.needleNodeId = needle.graph.nodes[j].nodeId; + mapping.needleUserData = needle.graph.nodes[j].userData; + mapping.haystackNodeId = haystack.graph.nodes[*enumerationMatrix[j].begin()].nodeId; + mapping.haystackUserData = haystack.graph.nodes[*enumerationMatrix[j].begin()].userData; + generatePortmapCandidates(portmapCandidates[j], enumerationMatrix, needle, haystack, j); + result.mappings[needle.graph.nodes[j].nodeId] = mapping; + } + + while (prunePortmapCandidates(portmapCandidates, enumerationMatrix, needle, haystack)) { } + + for (int j = 0; j < int(enumerationMatrix.size()); j++) { + if (portmapCandidates[j].size() == 0) { + if (verbose) { + printf("\nSolution (rejected by portmapper):\n"); + printEnumerationMatrix(enumerationMatrix, haystack.graph.nodes.size()); + } + return; + } + result.mappings[needle.graph.nodes[j].nodeId].portMapping = *portmapCandidates[j].begin(); + } + + if (!userSolver->userCheckSolution(result)) { + if (verbose) { + printf("\nSolution (rejected by userCheckSolution):\n"); + printEnumerationMatrix(enumerationMatrix, haystack.graph.nodes.size()); + } + return; + } + + for (int j = 0; j < int(enumerationMatrix.size()); j++) + haystack.usedNodes[*enumerationMatrix[j].begin()] = true; + + if (verbose) { + printf("\nSolution:\n"); + printEnumerationMatrix(enumerationMatrix, haystack.graph.nodes.size()); + } + + results.push_back(result); + return; + } + + if (verbose) { + printf("\n"); + printf("Enumeration Matrix at recursion level %d (%d):\n", iter, i); + printEnumerationMatrix(enumerationMatrix, haystack.graph.nodes.size()); + } + + std::set activeRow; + enumerationMatrix[i].swap(activeRow); + + for (int j : activeRow) + { + // found enough? + if (limitResults >= 0 && int(results.size()) >= limitResults) + return; + + // already used by other solution -> try next + if (!allowOverlap && haystack.usedNodes[j]) + continue; + + // create enumeration matrix for child in recursion tree + std::vector> nextEnumerationMatrix = enumerationMatrix; + for (int k = 0; k < int(nextEnumerationMatrix.size()); k++) + nextEnumerationMatrix[k].erase(j); + nextEnumerationMatrix[i].insert(j); + + // recursion + ullmannRecursion(results, nextEnumerationMatrix, iter+1, needle, haystack, allowOverlap, limitResults); + + // we just have found something -> unroll to top recursion level + if (!allowOverlap && haystack.usedNodes[j] && iter > 0) + return; + } + } + + // interface to the public Solver class + +protected: + SolverWorker(Solver *userSolver) : userSolver(userSolver), verbose(false) + { + } + + void setVerbose() + { + verbose = true; + } + + void addGraph(std::string graphId, const Graph &graph) + { + assert(graphData.count(graphId) == 0); + + GraphData &gd = graphData[graphId]; + gd.graphId = graphId; + gd.graph = graph; + diCache.add(gd.graph, gd.adjMatrix, graphId, userSolver); + } + + void addCompatibleTypes(std::string needleTypeId, std::string haystackTypeId) + { + compatibleTypes[needleTypeId].insert(haystackTypeId); + } + + void addCompatibleConstants(int needleConstant, int haystackConstant) + { + compatibleConstants[needleConstant].insert(haystackConstant); + } + + void addSwappablePorts(std::string needleTypeId, const std::set &ports) + { + swapPorts[needleTypeId].insert(ports); + diCache.compareCache.clear(); + } + + void addSwappablePortsPermutation(std::string needleTypeId, const std::map &portMapping) + { + swapPermutations[needleTypeId].insert(portMapping); + diCache.compareCache.clear(); + } + + void solve(std::vector &results, std::string needleGraphId, std::string haystackGraphId, + const std::map> &initialMappings, bool allowOverlap, int maxSolutions) + { + assert(graphData.count(needleGraphId) > 0); + assert(graphData.count(haystackGraphId) > 0); + + const GraphData &needle = graphData[needleGraphId]; + GraphData &haystack = graphData[haystackGraphId]; + + std::vector> enumerationMatrix; + generateEnumerationMatrix(enumerationMatrix, needle, haystack, initialMappings); + + if (verbose) + { + printf("\n"); + printf("Needle Adjecency Matrix:\n"); + printAdjMatrix(needle.adjMatrix); + + printf("\n"); + printf("Haystack Adjecency Matrix:\n"); + printAdjMatrix(haystack.adjMatrix); + + printf("\n"); + printf("Edge Types:\n"); + diCache.printEdgeTypes(); + + printf("\n"); + printf("Enumeration Matrix:\n"); + printEnumerationMatrix(enumerationMatrix, haystack.graph.nodes.size()); + } + + haystack.usedNodes.resize(haystack.graph.nodes.size()); + ullmannRecursion(results, enumerationMatrix, 0, needle, haystack, allowOverlap, maxSolutions > 0 ? results.size() + maxSolutions : -1); + } + + void clearOverlapHistory() + { + for (auto &it : graphData) + it.second.usedNodes.clear(); + } + + void clearConfig() + { + compatibleTypes.clear(); + compatibleConstants.clear(); + swapPorts.clear(); + swapPermutations.clear(); + diCache.compareCache.clear(); + } + + friend class Solver; +}; + +bool Solver::userCompareNodes(const std::string&, const std::string&, void*, const std::string&, const std::string&, void*) +{ + return true; +} + +std::string Solver::userAnnotateEdge(const std::string&, const std::string&, void*, const std::string&, void*) +{ + return std::string(); +} + +bool Solver::userCompareEdge(const std::string&, const std::string&, void*, const std::string&, void*, const std::string&, const std::string&, void*, const std::string&, void*) +{ + return true; +} + +bool Solver::userCheckSolution(const Result&) +{ + return true; +} + +SubCircuit::Solver::Solver() +{ + worker = new SolverWorker(this); +} + +SubCircuit::Solver::~Solver() +{ + delete worker; +} + +void SubCircuit::Solver::setVerbose() +{ + worker->setVerbose(); +} + +void SubCircuit::Solver::addGraph(std::string graphId, const Graph &graph) +{ + worker->addGraph(graphId, graph); +} + +void SubCircuit::Solver::addCompatibleTypes(std::string needleTypeId, std::string haystackTypeId) +{ + worker->addCompatibleTypes(needleTypeId, haystackTypeId); +} + +void SubCircuit::Solver::addCompatibleConstants(int needleConstant, int haystackConstant) +{ + worker->addCompatibleConstants(needleConstant, haystackConstant); +} + +void SubCircuit::Solver::addSwappablePorts(std::string needleTypeId, std::string portId1, std::string portId2, std::string portId3, std::string portId4) +{ + std::set ports; + ports.insert(portId1); + ports.insert(portId2); + ports.insert(portId3); + ports.insert(portId4); + ports.erase(std::string()); + addSwappablePorts(needleTypeId, ports); +} + +void SubCircuit::Solver::addSwappablePorts(std::string needleTypeId, std::set ports) +{ + worker->addSwappablePorts(needleTypeId, ports); +} + +void SubCircuit::Solver::addSwappablePortsPermutation(std::string needleTypeId, std::map portMapping) +{ + worker->addSwappablePortsPermutation(needleTypeId, portMapping); +} + +void SubCircuit::Solver::solve(std::vector &results, std::string needleGraphId, std::string haystackGraphId, bool allowOverlap, int maxSolutions) +{ + std::map> emptyInitialMapping; + worker->solve(results, needleGraphId, haystackGraphId, emptyInitialMapping, allowOverlap, maxSolutions); +} + +void SubCircuit::Solver::solve(std::vector &results, std::string needleGraphId, std::string haystackGraphId, + const std::map> &initialMappings, bool allowOverlap, int maxSolutions) +{ + worker->solve(results, needleGraphId, haystackGraphId, initialMappings, allowOverlap, maxSolutions); +} + +void SubCircuit::Solver::clearOverlapHistory() +{ + worker->clearOverlapHistory(); +} + +void SubCircuit::Solver::clearConfig() +{ + worker->clearConfig(); +} + diff --git a/libs/subcircuit/subcircuit.h b/libs/subcircuit/subcircuit.h new file mode 100644 index 00000000..da536ba0 --- /dev/null +++ b/libs/subcircuit/subcircuit.h @@ -0,0 +1,139 @@ +/* + * SubCircuit -- An implementation of the Ullmann Subgraph Isomorphism + * algorithm for coarse grain logic networks + * + * Copyright (C) 2013 Clifford Wolf + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#ifndef SUBCIRCUIT_H +#define SUBCIRCUIT_H + +#include +#include +#include +#include + +namespace SubCircuit +{ + class SolverWorker; + + class Graph + { + protected: + struct BitRef { + int nodeIdx, portIdx, bitIdx; + BitRef(int nodeIdx = -1, int portIdx = -1, int bitIdx = -1) : nodeIdx(nodeIdx), portIdx(portIdx), bitIdx(bitIdx) { }; + bool operator < (const BitRef &other) const; + }; + + struct Edge { + std::set portBits; + int constValue; + bool isExtern; + Edge() : constValue(0), isExtern(false) { }; + }; + + struct PortBit { + int edgeIdx; + PortBit() : edgeIdx(-1) { }; + }; + + struct Port { + std::string portId; + int minWidth; + std::vector bits; + Port() : minWidth(-1) { }; + }; + + struct Node { + std::string nodeId, typeId; + std::map portMap; + std::vector ports; + void *userData; + Node() : userData(NULL) { }; + }; + + bool allExtern; + std::map nodeMap; + std::vector nodes; + std::vector edges; + + public: + Graph() : allExtern(false) { }; + + void createNode(std::string nodeId, std::string typeId, void *userData = NULL); + void createPort(std::string nodeId, std::string portId, int width = 1, int minWidth = -1); + void createConnection(std::string fromNodeId, std::string fromPortId, int fromBit, std::string toNodeId, std::string toPortId, int toBit, int width = 1); + void createConnection(std::string fromNodeId, std::string fromPortId, std::string toNodeId, std::string toPortId); + void createConstant(std::string toNodeId, std::string toPortId, int toBit, int constValue); + void createConstant(std::string toNodeId, std::string toPortId, int constValue); + void markExtern(std::string nodeId, std::string portId, int bit = -1); + void markAllExtern(); + void print(); + + friend class SolverWorker; + }; + + class Solver + { + public: + struct ResultNodeMapping { + std::string needleNodeId, haystackNodeId; + void *needleUserData, *haystackUserData; + std::map portMapping; + }; + struct Result { + std::string needleGraphId, haystackGraphId; + std::map mappings; + }; + + private: + SolverWorker *worker; + + protected: + virtual bool userCompareNodes(const std::string &needleGraphId, const std::string &needleNodeId, void *needleUserData, + const std::string &haystackGraphId, const std::string &haystackNodeId, void *haystackUserData); + + virtual std::string userAnnotateEdge(const std::string &graphId, const std::string &fromNodeId, void *fromUserData, const std::string &toNodeId, void *toUserData); + + virtual bool userCompareEdge(const std::string &needleGraphId, const std::string &needleFromNodeId, void *needleFromUserData, const std::string &needleToNodeId, void *needleToUserData, + const std::string &haystackGraphId, const std::string &haystackFromNodeId, void *haystackFromUserData, const std::string &haystackToNodeId, void *haystackToUserData); + + virtual bool userCheckSolution(const Result &result); + + friend class SolverWorker; + + public: + Solver(); + ~Solver(); + + void setVerbose(); + void addGraph(std::string graphId, const Graph &graph); + void addCompatibleTypes(std::string needleTypeId, std::string haystackTypeId); + void addCompatibleConstants(int needleConstant, int haystackConstant); + void addSwappablePorts(std::string needleTypeId, std::string portId1, std::string portId2, std::string portId3 = std::string(), std::string portId4 = std::string()); + void addSwappablePorts(std::string needleTypeId, std::set ports); + void addSwappablePortsPermutation(std::string needleTypeId, std::map portMapping); + + void solve(std::vector &results, std::string needleGraphId, std::string haystackGraphId, bool allowOverlap = true, int maxSolutions = -1); + void solve(std::vector &results, std::string needleGraphId, std::string haystackGraphId, + const std::map> &initialMapping, bool allowOverlap = true, int maxSolutions = -1); + void clearOverlapHistory(); + void clearConfig(); + }; +} + +#endif /* SUBCIRCUIT_H */ diff --git a/libs/subcircuit/test_large.spl b/libs/subcircuit/test_large.spl new file mode 100644 index 00000000..74a47d94 --- /dev/null +++ b/libs/subcircuit/test_large.spl @@ -0,0 +1,221 @@ +#!/usr/bin/env splrun + +var idx = 0; +var count_nand = 0; +var count_nor = 0; + +function makeNAND(net, id) +{ + count_nand++; + + net["${id}_VDD"] = "${id}_pa S"; + net["${id}_VSS"] = "${id}_nb S"; + + net["${id}_A"] = "${id}_pa G"; + net["${id}_B"] = "${id}_pb G"; + net["${id}_Y"] = "${id}_pb D"; + + return <:> + : node ${id}_pa pmos S 1 D 1 G 1 + : node ${id}_pb pmos S 1 D 1 G 1 + : node ${id}_na nmos S 1 D 1 G 1 + : node ${id}_nb nmos S 1 D 1 G 1 + : connect ${id}_pa S ${id}_pb S + : connect ${id}_pa D ${id}_pb D + : connect ${id}_pa D ${id}_na D + : connect ${id}_na S ${id}_nb D + : connect ${id}_pa G ${id}_na G + : connect ${id}_pb G ${id}_nb G + ; +} + +function makeNOR(net, id) +{ + count_nor++; + + net["${id}_VDD"] = "${id}_pa S"; + net["${id}_VSS"] = "${id}_nb S"; + + net["${id}_A"] = "${id}_pa G"; + net["${id}_B"] = "${id}_pb G"; + net["${id}_Y"] = "${id}_pb D"; + + return <:> + : node ${id}_pa pmos S 1 D 1 G 1 + : node ${id}_pb pmos S 1 D 1 G 1 + : node ${id}_na nmos S 1 D 1 G 1 + : node ${id}_nb nmos S 1 D 1 G 1 + : connect ${id}_pa D ${id}_pb S + : connect ${id}_pb D ${id}_na D + : connect ${id}_pb D ${id}_nb D + : connect ${id}_na S ${id}_nb S + : connect ${id}_pa G ${id}_na G + : connect ${id}_pb G ${id}_nb G + ; +} + +function makeGraph(seed, gates, primaryInputs, primaryOutputs) +{ + srand(seed); + + var code = ""; + var net, vdd, vss, outputs; + var unusedOutpus; + for (var i = 0; i < gates; i++) + { + var id = fmt("G%d", idx++); + if (rand(2) == 0) + code ~= makeNAND(net, id); + else + code ~= makeNOR(net, id); + + if (i == 0) { + vdd = net["${id}_VDD"]; + vss = net["${id}_VSS"]; + } else { + code ~= <:> + : connect $vdd ${net["${id}_VDD"]} + : connect $vss ${net["${id}_VSS"]} + ; + } + + var inIdx1 = rand((elementsof outputs) + 1); + if (inIdx1 < elementsof outputs) { + code ~= " connect ${outputs[inIdx1]} ${net["${id}_A"]}\n"; + delete unusedOutpus[outputs[inIdx1]]; + } else + push primaryInputs, net["${id}_A"]; + + var inIdx2 = rand((elementsof outputs) + 1); + if (inIdx2 < elementsof outputs) { + code ~= " connect ${outputs[inIdx2]} ${net["${id}_B"]}\n"; + delete unusedOutpus[outputs[inIdx2]]; + } else + push primaryInputs, net["${id}_B"]; + + unusedOutpus[net["${id}_Y"]] = 1; + push outputs, net["${id}_Y"]; + } + + foreach netDecl (unusedOutpus) + push primaryOutputs, netDecl; + + return code; +} + +function makeConnections(fromNets, toNets) +{ + var code = ""; + foreach[] toNet (toNets) { + var fromNet = fromNets[rand(elementsof fromNets)]; + code != " connect $fromNet $toNet\n"; + } + return code; +} + +var numNodes; + +write(<:> + : graph nand + + ${makeNAND(net, "nand")} + : extern ${net["nand_VDD"]} + : extern ${net["nand_VSS"]} + : extern ${net["nand_A"]} + : extern ${net["nand_B"]} + : extern ${net["nand_Y"]} + : endgraph + : + : graph nor + ${makeNOR(net, "nor")} + : extern ${net["nor_VDD"]} + : extern ${net["nor_VSS"]} + : extern ${net["nor_A"]} + : extern ${net["nor_B"]} + : extern ${net["nor_Y"]} + : endgraph + : + : graph needle_1 + + ${makeGraph(1, 100, ports, ports)} + + + : extern $net + + : endgraph + : + : graph needle_2 + + ${makeGraph(2, 200, ports, ports)} + + + : extern $net + + : endgraph + : + : graph needle_3 + + ${makeGraph(3, 300, ports, ports)} + + + : extern $net + + : endgraph + : + : graph haystack + + + + + ${makeGraph(1, 100, inPorts1, outPorts1)} + + + ${makeGraph(2, 200, inPorts2, outPorts2)} + + + ${makeGraph(3, 300, inPorts3, outPorts3)} + + + ${makeGraph(2, 200, inPorts4, outPorts4)} + + + ${makeGraph(1, 100, inPorts5, outPorts5)} + + + ${makeConnections(outPorts1, inPorts2)} + ${makeConnections(outPorts2, inPorts3)} + ${makeConnections(outPorts3, inPorts4)} + ${makeConnections(outPorts4, inPorts5)} + + : endgraph + : + : solve nand haystack false + : expect $count_nand + : clearoverlap + : + : solve nor haystack false + : expect $count_nor + : clearoverlap + : + : solve needle_1 haystack false + : expect 2 + : + : solve needle_2 haystack false + : expect 2 + : + : solve needle_3 haystack false + : expect 1 +); + +numNodes["haystack"] -= numNodes["needle_3"]; +numNodes["needle_3"] -= numNodes["needle_2"]; +numNodes["needle_2"] -= numNodes["needle_1"]; + +write(<:> + : + : # Needle_1: ${numNodes["needle_1"]} transistors + : # Needle_2: ${numNodes["needle_2"]} transistors + : # Needle_3: ${numNodes["needle_3"]} transistors + : # Haystack: ${numNodes["haystack"]} transistors +); + diff --git a/libs/subcircuit/test_macc22.txt b/libs/subcircuit/test_macc22.txt new file mode 100644 index 00000000..71938c1c --- /dev/null +++ b/libs/subcircuit/test_macc22.txt @@ -0,0 +1,48 @@ + +# verbose + +graph macc22 + node mul_1 mul A 32 B 32 Y 32 + node mul_2 mul A 32 B 32 Y 32 + node add_1 add A 32 B 32 Y 32 + connect mul_1 Y add_1 A + connect mul_2 Y add_1 B + extern mul_1 A B + extern mul_2 A B + extern add_1 Y +endgraph + +graph macc4x2 + node mul_1 mul A 32 B 32 Y 32 + node mul_2 mul A 32 B 32 Y 32 + node mul_3 mul A 32 B 32 Y 32 + node mul_4 mul A 32 B 32 Y 32 + node add_1 add A 32 B 32 Y 32 + node add_2 add A 32 B 32 Y 32 + node add_3 add A 32 B 32 Y 32 + connect mul_1 Y add_1 A + connect mul_2 Y add_1 B + connect mul_3 Y add_2 A + connect mul_4 Y add_2 B + connect add_1 Y add_3 A + connect add_2 Y add_3 B + extern mul_1 A B + extern mul_2 A B + extern mul_3 A B + extern mul_4 A B + extern add_3 Y +endgraph + +solve macc22 macc4x2 +expect 2 + +swapgroup mul A B + +solve macc22 macc4x2 +expect 2 + +swapperm add A B : B A + +solve macc22 macc4x2 +expect 4 + diff --git a/libs/subcircuit/test_perm.pl b/libs/subcircuit/test_perm.pl new file mode 100644 index 00000000..b4e05e35 --- /dev/null +++ b/libs/subcircuit/test_perm.pl @@ -0,0 +1,108 @@ +#!/usr/bin/perl -w + +use strict; + +# let "macc" implement a function like Y = (A*B) + (C*D) +# +# the following permutations of the input pins exist: +# +# g01 | A B C D | match +# g02 | A B D C | match +# g03 | A C B D | not +# g04 | A C D B | not +# g05 | A D B C | not +# g06 | A D C B | not +# g07 | B A C D | match +# g08 | B A D C | match +# g09 | B C A D | not +# g10 | B C D A | not +# g11 | B D A C | not +# g12 | B D C A | not +# g13 | C A B D | not +# g14 | C A D B | not +# g15 | C B A D | not +# g16 | C B D A | not +# g17 | C D A B | match +# g18 | C D B A | match +# g19 | D A B C | not +# g20 | D A C B | not +# g21 | D B A C | not +# g22 | D B C A | not +# g23 | D C A B | match +# g24 | D C B A | match + +my @matches = qw/g01 g02 g07 g08 g17 g18 g23 g24/; +my @non_matches = qw/g03 g04 g05 g06 g09 g10 g11 g12 g13 g14 g15 g16 g19 g20 g21 g22/; + +print "\n"; + +for my $i (0..3) { +for my $j (0..2) { +for my $k (0..1) { + my @t = qw/A B C D/; + print "# "; + print splice(@t,$i,1),splice(@t,$j,1),splice(@t,$k,1),$t[0]; + print "\n"; +}}} + +print "\n"; + +my $iter = 1; +for my $i (0..3) { +for my $j (0..2) { +for my $k (0..1) { + my @t = qw/A B C D/; + printf "graph g%02d\n", $iter++; + printf " node input input A 32 1 B 32 1 C 32 1 D 32 1\n"; + printf " node macc macc A 32 1 B 32 1 C 32 1 D 32 1\n"; + printf " connect input A macc %s\n", splice(@t,$i,1); + printf " connect input B macc %s\n", splice(@t,$j,1); + printf " connect input C macc %s\n", splice(@t,$k,1); + printf " connect input D macc %s\n", splice(@t,0,1); + printf "endgraph\n"; + printf "\n"; +}}} + +$iter = 1; +printf "graph gXL\n"; +for my $i (0..3) { +for my $j (0..2) { +for my $k (0..1) { + my $id = sprintf "_%02d", $iter++; + my @t = qw/A B C D/; + printf " node input$id input A 16 B 16 C 16 D 16\n"; + printf " node macc$id macc A 16 B 16 C 16 D 16\n"; + printf " connect input$id A macc$id %s\n", splice(@t,$i,1); + printf " connect input$id B macc$id %s\n", splice(@t,$j,1); + printf " connect input$id C macc$id %s\n", splice(@t,$k,1); + printf " connect input$id D macc$id %s\n", splice(@t,0,1); +}}} +printf "endgraph\n"; +printf "\n"; + + +printf "swapgroup macc A B\n"; +printf "swapgroup macc C D\n"; +printf "swapperm macc A B C D : C D A B\n"; + +for my $i (@matches) { +for my $j (@non_matches) { + printf "solve %s %s\n", $i, $j; +}} +printf "expect 0\n\n"; + +for my $i (@matches) { +for my $j (@matches) { + printf "solve %s %s\n", $i, $j; +}} +printf "expect %d\n\n", @matches*@matches; + +printf "solve g01 gXL false\n"; +printf "expect 8\n"; + +printf "solve g03 gXL false\n"; +printf "expect 8\n"; + +printf "solve g04 gXL false\n"; +printf "expect 8\n"; + diff --git a/libs/subcircuit/test_shorts.spl b/libs/subcircuit/test_shorts.spl new file mode 100644 index 00000000..f1cb4cfd --- /dev/null +++ b/libs/subcircuit/test_shorts.spl @@ -0,0 +1,121 @@ +#!/usr/bin/env splrun +// +// Test procedure for matching Gates with shorted inputs, as suggested in +// "SubCircuit Extraction with SubGraph Isomorphism. Zong Ling, Ph. D. IBM +// Almaden Research Center -- EDA Shape Processing zling@us.ibm.com.": +// +// Four NAND gates and a NOR gate. One NAND gate (G1) has no shorted inputs, +// one (G2) has an input shorted to VSS, one (G3) has an input shorted to VDD, +// and one (G4) has both inputs shorted together. Th last gate (G5) is a NOR +// gate. + +var net; + +function makeNAND(id) +{ + net["${id}_VDD"] = "${id}_pa S"; + net["${id}_VSS"] = "${id}_nb S"; + + net["${id}_A"] = "${id}_pa G"; + net["${id}_B"] = "${id}_pb G"; + net["${id}_Y"] = "${id}_pb D"; + + return <:> + : node ${id}_pa pmos S 1 D 1 G 1 + : node ${id}_pb pmos S 1 D 1 G 1 + : node ${id}_na nmos S 1 D 1 G 1 + : node ${id}_nb nmos S 1 D 1 G 1 + : connect ${id}_pa S ${id}_pb S + : connect ${id}_pa D ${id}_pb D + : connect ${id}_pa D ${id}_na D + : connect ${id}_na S ${id}_nb D + : connect ${id}_pa G ${id}_na G + : connect ${id}_pb G ${id}_nb G + ; +} + +function makeNOR(id) +{ + net["${id}_VDD"] = "${id}_pa S"; + net["${id}_VSS"] = "${id}_nb S"; + + net["${id}_A"] = "${id}_pa G"; + net["${id}_B"] = "${id}_pb G"; + net["${id}_Y"] = "${id}_pb D"; + + return <:> + : node ${id}_pa pmos S 1 D 1 G 1 + : node ${id}_pb pmos S 1 D 1 G 1 + : node ${id}_na nmos S 1 D 1 G 1 + : node ${id}_nb nmos S 1 D 1 G 1 + : connect ${id}_pa D ${id}_pb S + : connect ${id}_pb D ${id}_na D + : connect ${id}_pb D ${id}_nb D + : connect ${id}_na S ${id}_nb S + : connect ${id}_pa G ${id}_na G + : connect ${id}_pb G ${id}_nb G + ; +} + +write(<:> + : graph nand + : ${ makeNAND("G0") } + : extern ${net["G0_VDD"]} + : extern ${net["G0_VSS"]} + : extern ${net["G0_A"]} + : extern ${net["G0_B"]} + : extern ${net["G0_Y"]} + : endgraph + : + : graph nor + : ${ makeNOR("G0") } + : extern ${net["G0_VDD"]} + : extern ${net["G0_VSS"]} + : extern ${net["G0_A"]} + : extern ${net["G0_B"]} + : extern ${net["G0_Y"]} + : endgraph + : + : graph haystack + : ${ makeNAND("G1") } + : ${ makeNAND("G2") } + : ${ makeNAND("G3") } + : ${ makeNAND("G4") } + ${ makeNOR("G5") } + : + : node vdd vsupply V 1 + : connect vdd V ${net["G1_VDD"]} + : connect vdd V ${net["G2_VDD"]} + : connect vdd V ${net["G3_VDD"]} + : connect vdd V ${net["G4_VDD"]} + : connect vdd V ${net["G5_VDD"]} + : + : node vss vsupply V 1 + : connect vss V ${net["G1_VSS"]} + : connect vss V ${net["G2_VSS"]} + : connect vss V ${net["G3_VSS"]} + : connect vss V ${net["G4_VSS"]} + : connect vss V ${net["G5_VSS"]} + : + : connect ${net["G2_A"]} ${net["G1_A"]} + : connect ${net["G2_B"]} ${net["G2_VSS"]} + : + : connect ${net["G3_A"]} ${net["G1_VDD"]} + : connect ${net["G3_B"]} ${net["G2_Y"]} + : + : connect ${net["G4_A"]} ${net["G1_Y"]} + : connect ${net["G4_B"]} ${net["G1_Y"]} + : + : connect ${net["G5_A"]} ${net["G3_Y"]} + : connect ${net["G5_B"]} ${net["G4_Y"]} + : endgraph + : + : solve nand haystack false + : clearoverlap + : expect 4 + : + : solve nor haystack false + : clearoverlap + : expect 1 +); + -- cgit v1.2.3