4.2.4 Accelerating the Simulator

   All SET circuits have an infinite state space, except some very simple circuits without any island, because the possible excess charge on islands is unbound. Nevertheless, very often only a limited number of states determine the behavior of a circuit. This characteristic may be exploited to considerably speed up a MC based SET simulator. For every time step tunnel rates for every possible tunnel event are computed. Since only a limited number of states dominate the circuit, the simulator will repeatedly step into states that have been visited before. Instead of recalculating all possible tunnel rates again and again one can store that information for later use. Essential is that the average search time for an already stored data set is less than the time for a recalculation of the tunnel rates. The insertion time of a new data set is not crucial, since the ratio of simulated tunnel events to visited states is generally much larger than one, which means that there will be much more look-ups than new state data to store. A straight forward approach would be to number states according to their charge distribution, which is an integer number for every island. Then each state would be directly addressable with its unique state number, without the need for searching. However, the memory requirement for such a storage scheme grows exponentially with island number (more precisely with the number of charge-nodes), which is not acceptable except for very simple circuits with only a few islands. Clearly this is not suitable for a multipurpose SET simulator which should be capable of simulating circuits with many islands. Our method of choice for storing computed tunnel rates was therefore a hash table. Hash tables have the suitable feature of very short search times which depend on the quality of the hash function and the relative filling rate of the table [63]. A sufficiently hashed index may be derived from the number of excess charge carriers on islands. The only difficulty one has to deal with is that the number of states the circuit will visit is unknown, and so is the size of the hash table needed, to prevent a too high filling rate. The filling of a hash table should be kept below 90%. Otherwise the performance degrades drastically. Nevertheless a variety of techniques exist, which can cope with this problem. Knuth [63] explains methods that combine linked lists or binary search trees with a hash table.

With a double hashed table we achieved an acceleration of a factor between 5 and 10.