ZRELY1 - Reliability of Logic Circuits

no tags 

Combinational logic circuits are part of all modern CPUs and other electronic means of information processing. These processors are widely used and constantly grow in complexity. Number of transistors in a modern CPU has exceeded 2 billion?. And it looks like this growth does not tend to stop. At the same time, technological processes of processor production shrink. Transistors become smaller and more vulnerable to external influences. And now, even far from the strongest external radiation or magnetic field can lead to short-term changes in the logical values of microelectronic circuits. This problem is especially acute in space systems and other systems critical to reliability. In this problem, we pose the question, how to make the circuit more resilient to external influences knowing its logic? Your task is to develop an algorithm for creating such a reliable circuit.

Let a logic circuit without feedback or memory elements is given, consisting of the following 6 elements:

Name Description Operation Figure
AND logical «AND» OUT=A&B AND
OR logical «OR» OUT=A|B OR
NAND inverted AND OUT=!(A&B) NAND
NOR inverted OR OUT=!(A|B) NOR
XOR exclusive «OR» OUT=A^B XOR

The circuit is affected by environmental noise changing gate logical value to the opposite with a certain probability. Your task is to construct a circuit which has the same logic function as the original one, but is less prone to failures. Under the terms of the problem the circuit that you construct should exceed the initial area no more than "K" times .

One of the parameters which characterize failure tolerance of logic circuits is COF – “Total circuit failure resistance factor”. COF is calculated as the ratio of the number of correct results of circuit performance (all circuit outputs must have correct value) to the total number of the performed tests. Accordingly, for the most reliable circuits COF tends to 1.

Every logic gate of the circuit is characterized by the following parameters: S – gate area, p – failure probability (in percent) under current external conditions.

Input data

The first line shows Z – the number of tests (Z < 400). This is followed by Z tests .

The first line of each test shows the number K (2.0 ≤ K ≤ 20.0) - maximum circuit area redundancy.

The following six lines contain two numbers each: area S (1 ≤ S ≤ 100) and failure probability q (0 ≤ q ≤ 20) in percent, Parameters of each of the logic gates are given in the following order: INV, AND, OR, NAND, NOR, XOR.

The next line shows the number “I” (0 < I < 250) – the number of circuit inputs, followed by I lines, no more than 20 characters each, separated by spaces – the names of the input nodes of the circuit.

The next line shows the number “O” (0 < O < 150) – the number of circuit outputs, followed by O lines, no more than 20 characters each, separated by spaces – the names of the output nodes of the circuit.

Then the number of logic gates in the circuit N (1 < N < 5000) is stated, followed by N lines with the description of each gate.

Description of each gate begins with its type, next come the names of the input nodes, then the name of the output node

Output data

For each test you should present the circuit description of in the following format. In the first line number N (1 < N < 100000) – the number of gates in the resulting circuit. This is followed by N – lines with the gates description. Each gate description begins with its type, next come the names of the input nodes, followed by the name of the output node.


The number of scored points Score is summed over all tests. The number of points received for a test is equal to COF value calculated for your circuit. COF is calculated by Monte Carlo method? in two steps:

1) in the first step, the judge determines that your circuit works identically to the original one. The same test sequences (several thousand) are fed to the inputs of both circuits and Boolean values at the outputs of the circuits are compared. If the logical values differ, you get the status of Wrong Answer. Also, the judge checks that the given circuit redundancy was not exceeded.

2) in the second step, the judge will invert the values on your circuit gates randomly with the given probability and compare the output values for your circuit and the benchmark circuit. If at least one of the outputs will be different, «wrong answers» counter will be increased. Formula used for calculation: COF = (TT - INC)/TT, where:
TT - total number of tests
INC - number of tests, where at least one output of the circuit manifested error

From final score we extract C=276 points, which somewhere equal default soultion. If final score lower than 276 it'll recieve 0 points.


Input data:

Let logic circuit is given (see the figure). Required redundancy should not be more than 4.1 times. The circuit is based on the library, for which:

INV has area 50 and failure probability 3%

AND has area 60 and failure probability 3.1%

OR has area 60 and failure probability 3.2%

NAND has area 70 and failure probability 3.3%

NOR has area 70 and failure probability 3.4%

XOR has area 70 and failure probability 3.5%

Input file for this task looks as follows:

50.0 3.0
60.0 3.1
60.0 3.2
70.0 3.3
70.0 3.4
70.0 3.5
2 a b
2 cs cc
INV a n1
INV b n2
NAND a b cc
NAND n1 n2 n3
NAND n3 cc cs

Output data:

Let our algorithm uses standard triplication technique and selection of a Boolean value which is used on the majority of outputs (Triple Modular Redundancy (TMR)?). In this case, the output file can be written as follows:

INV a n1_a0
INV a n1_a1
INV a n1_a2
INV b n2_a0
INV b n2_a1
INV b n2_a2
NAND a b cc_a0
NAND a b cc_a1
NAND a b cc_a2
NAND n1_a0 n2_a0 n3_a0
NAND n1_a1 n2_a1 n3_a1
NAND n1_a2 n2_a2 n3_a2
NAND n3_a0 cc_a0 cs_a0
NAND n3_a1 cc_a1 cs_a1
NAND n3_a2 cc_a2 cs_a2
AND cs_a0 cs_a1 cs_3_0_and_0_out
AND cs_a0 cs_a2 cs_5_0_and_0_out
AND cs_a1 cs_a2 cs_6_0_and_0_out
OR cs_3_0_and_0_out cs_5_0_and_0_out cs_0_or_0_out
OR cs_0_or_0_out cs_6_0_and_0_out cs
AND cc_a0 cc_a1 cc_3_0_and_0_out
AND cc_a0 cc_a2 cc_5_0_and_0_out
AND cc_a1 cc_a2 cc_6_0_and_0_out
OR cc_3_0_and_0_out cc_5_0_and_0_out cc_0_or_0_out
OR cc_0_or_0_out cc_6_0_and_0_out cc

Figure for the resulting file


After simulation this solution will score 0.682661 points.

Useful files:

1) Simple solution C/C++ - program reads the data and prints the circuit as it is, without changes.
2) Judge at C/C++ - program, which is used on the server for evaluation of the solution. Can be used locally to test the effectiveness of your solution.
3) Test data set - a set of 102 test circuits, similar to a set on the server.

hide comments
Roman Sol: 2015-02-16 14:11:35

Flago, yeah I thought about this coefficient, but tried to avoid complicated scoring system. But now I see you right, psychologically difference between 276.1058 and 295.6856 too small than between 0.1058 and 20.6856 ) I will change it in few days.

Flago: 2015-02-16 14:11:35

Ty for the changes, might give it a fair try now some day :)

Maybe something like :

new_score = old_score > 276 ? old_score - 276 : 0 ;

Might be better for SPOJ score system, since now "basic" solution give almost perfect score.

Last edit: 2015-02-11 16:52:49
Roman Sol: 2015-02-16 14:11:35

The scoring system was changed. Now TT means "total number of tests". Now "trash gate" scenario doesn't work, but the difference between solutions became smaller.

All soultions were rejudjed.

Last edit: 2015-02-09 12:53:25
Roman Sol: 2015-02-16 14:11:35

Flago, thank you now I get it ) I probably will change the judge to avoid this. Need to think how to make it. Probably I should consider floating nodes as outputs also.

Flago: 2015-02-16 14:11:35

@Roman Sol : Nope, changing the seed might give you some (very) little changes on score but it won't give those result just by adding trash gates. I will give you a concrete exemple of the "trash gate abuse".

Let our exemple have the following input :
INV 50 20.0
1 a
1 c
INV a b
INV b c

So it is just a simple : [ a ==(INV)==> b ==(INV)==> c ], with 20% fail on each gate.

Let be our first solution the same circuit :
INV a b (gate A)
INV b c (gate B)

We have 4 possibilities with the following odds :
4% all fails, taken in count, correct output.
32% A or B fails, taken in count, incorrect output.
64% no fails, NOT taken in count.

Our score for that solution will be ( 0.36 - 0.32 ) / 0.36 = 0.111

Now, let add a trash gate to the solution ! Being the circuit :
INV a b (gate A)
INV b c (gate B)
INV a t (gate T)

We have 8 posibilities with the following odds :
0.8% all fails, taken in count, correct output.
3.2% A and B fails, taken in count, correct output.
6.4% A and T or B and T fails, taken in count, incorrect output.
12.8% T fails, taken in count, correct output (This one is the scam !).
25.6% A or B fails, taken in count, incorrect output.
51.2% No fails, NOT taken in count.

Our score for that solution will be ( 0.488 - 0.256 - 0.064 ) / 0.488 = 0.344 !!
Our score was improved just by cheating the score system, not improving the reliability what so ever.

Won't do the calculations, but we could improve futher more our score by adding yet another trash gate, and so on until the space is missing.

For information, my "best" score was obtained mainly by outputing the same circuit with a bunch of added trash gates. And changing some really little things just to gain the last decimal to get #1 :s

Roman Sol: 2015-02-16 14:11:35

Flago, actually I don't get it. Why you recieve better score with trash gates? If you don't have these gates you get correct or incorrect as well. And the probability of error of "usefull" gates stays the same. And the error flag set indpendently for any gate. So I think trash gates only can violate "seed" value for random generator. And you get better score not because of trash invertors, but because of random generator generates other values.

Flago: 2015-02-16 14:11:35

Enjoyed this problem.

@Problem setter : The score is however really poorly calculated. Taking in count only the number of test case where you had at least 1 failing gate make it abusable, for exemple, adding a bunch of "trash" gates at the end of you circuit like this (where "a" is any node of your circuit) :

INV a im_le_trash_gate_0
INV a im_le_trash_gate_1
INV a im_le_trash_gate_2
... (while you have the area to add more gates)

In a case that none of your legit gates fail but at least one of the trash gates does, the result is taking in count as correct case while it was not taking in count previously, improving your score without any improve on your output reliability.

Added by:Roman Sol
Time limit:50s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64