Member Avatar for Niketh

hi all,

I am working on C++ coding of fault simulation algorithm of a digital circuit . The first step involves parsing of netlist files. The sample netlist looks like -

# Only 2,3 input gates considered ...
INPUT(1)
INPUT(2)
INPUT(3)
INPUT(6)
INPUT(7)
OUTPUT(22)
OUTPUT(23)
# comment here

10 = NAND(1, 3)
11 = NAND(3, 6)
16 = NAND(2, 11)
19 = NAND(11, 7)
22 = NAND(10, 16)
23 = NAND(16, 19)

INPUT are the primary inputs, OUTPUT are the primary outputs, gates are the intermediate nodes. I hope some of you can imagine how this circuit will look like (..:)..).I have attached a sample image file of the above circuit. At this stage i have been able to extract all relevant numbers/values and gate type from the file.

My concern is what are the appropriate data structures that i can use to model the above circuit , so that i will be able to do the following :-

1) given bool values to the inputs , i can propagate it through the intermediate nodes to the output nodes.

2) To each node , i can add customary features like fan-in array, fan-out array.

I have tried out singly linked lists . Is it possible for a node to be pointed by multiple nodes(node1,2,3...) and a node to point to multiple nodes ? And also to be able to ascertain as from which node(node1,2,3...) is the current node traversed from ? Is it possible to propagate an integer value from one node to the other ?

In that case it would be slightly helpful . Any help as earlier as possible will be appreciated.

Thank you in advance
Regards
Niketh

circuit.png 5.56 KB
  • 3 Contributors
  • 2 Replies
  • 626 Views
  • 8 Months Discussion Span
  • Latest Post Latest Post by hactor

Dani AI

Generated

As suggested, think in terms of a directed graph (DAG) rather than a linked list: each gate is a node, wires are directed edges, and each node keeps a fan‑in list and a fan‑out list. For C++ implementations the pragmatic, high‑performance choices are: store nodes contiguously in a std::vector<Node> and use integer indices (or stable IDs) to reference other nodes, and keep an unordered_map<int,int> to map net IDs from the file to vector indices. Using indices avoids pointer invalidation and improves cache locality for large ISCAS nets.

A compact node model and a levelized evaluator are often enough and easy to debug:

enum GateType { INPUT, OUTPUT, NAND, NOR, INV /* etc. */ };

struct Node {
    int net_id;                 // original net number from file
    GateType type;
    std::vector<int> fin;       // indices of driving nodes
    std::vector<int> fout;      // indices of driven nodes
    uint8_t value;              // single-pattern: 0=0,1=1,2=X
    uint64_t bits;              // bit-parallel patterns (each bit = one pattern)
};

std::vector<Node> nodes;
std::vector<int> topo_order;   // compute once with Kahn's algorithm, then evaluate in this order

Evaluation approaches:

  • Pull (recursive) evaluation is simple and matches 's advice, but recursion depth can overflow on deep paths.
  • Levelized/topological pass (recommended for repeated simulation) computes nodes once per pattern set and is iterative and fast.
  • Event-driven (queue of changed nodes) is best when only a few signals change per vector.

Fault simulation notes: use a small multi-valued representation (0,1,X plus D/D') or two bitmasks per node to encode D/D' for stuck‑at analysis. For speed, pack many patterns into uint64_t words and do bitwise gate ops (AND/OR/NOT) to simulate 64 patterns in parallel.

Parsing & robustness tips: ignore comments, create placeholder nodes when a net is referenced before its definition, detect cycles via failed topological sort, validate fan‑in counts, and build fanout lists while you parse so injecting faults and propagating effects is O(fanout). Mentioning : keep test inputs small while validating the parser and evaluator before scaling to full ISCAS files.

Recommended Answers

All 2 Replies

Member Avatar for nezachem

I don't think a linked list is a right approach. You need a dependency graph, along the lines of

struct gate {
    bool result;
    bool resolved;
    gate * dep1;
    gate * dep2;
};

To calculate the output, you just simply traverse the graph starting from the output gate (remember, pull is almost always better than push):

gate::calculate()
{
    if(!resolved) {
        bool val1 = dep1->calculate();
        bool val2 = dep2->calculate();
        result = nand(val1, val2);
        resolved = true;
    }
    return result;
}

Of course, if some gates require more than one input (and/or perform functions other than nand), replace dep1 and dep2 with std::vector<gate *> dependency , and replace nand a virtual method.

Member Avatar for hactor

Hello thats sound a very interesting project. You have all done fine ?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.