** Next:** 5 Applications
** Up:** 4.2 Code structure
** Previous:** Step Size

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.

** Next:** 5 Applications
** Up:** 4.2 Code structure
** Previous:** Step Size

*Christoph Wasshuber*