GENERATING LEARNED REPRESENTATIONS OF DIGITAL CIRCUIT DESIGNS

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for generating learned representations of digital circuit designs. One of the systems includes obtaining data representing a program that implements a digital circuit design, the program comprising a plurality of statements; processing the obtained data to generate data representing a graph representing the digital circuit design, the graph comprising: a plurality of nodes representing respective statements of the program, a plurality of first edges each representing a control flow between a pair of statements of the program, and a plurality of second edges each representing a data flow between a pair of statements of the program; and generating a learned representation of the digital circuit design, comprising processing the data representing the graph using a graph neural network to generate a respective learned representation of each statement represented by a node of the graph.

BACKGROUND

This specification relates to neural networks.

SUMMARY

This specification describes a system implemented as computer programs on one or more computers in one or more locations that is configured to process data representing the design of a digital circuit to generate a machine-learned representation of the design (or, equivalently, a machine-learned representation of digital circuits manufactured according to the design). The system can then process the learned representation of the digital circuit design using one or more prediction neural networks to generate respective predictions about the digital circuit design.

Using techniques described in this specification, a system can generate machine-learned representations of digital circuit designs, and use the machine-learned representations for multiple different downstream tasks. The machine-learned representations can encode information about the attributes of the digital circuit design as well as source code information from the program statements used to implement the circuit.

Existing systems that perform verification on a digital circuit designs can require different hand-designed tests for each new design, requiring hundreds or thousands of expert engineer-hours. Using some techniques described in this specification, a trained neural network can automatically generate new tests for a given digital circuit design.

Executing hand-designed tests can require significant time and computational costs, sometimes taking multiple hours or days to do a single suite of tests. Using some techniques described in this specification, a system can predict, with high accuracy, the outcome of a particular test significantly more quickly. For example, in some implementations, generating a prediction for the outcome of a test only requires a single forward pass through the trained neural network, which can take, e.g., a few seconds or a fraction of a second. Providing instant feedback to engineers of the digital circuit design can significantly improve the efficiency of the process of designing a new circuit, allowing the engineers to test more designs and iterate much more quickly.

DETAILED DESCRIPTION

This specification describes a system implemented as computer programs on one or more computers in one or more locations that is configured to generate synthetic images using a self-attention based neural network.

FIG.1is a diagram of an example neural network system100that is configured to generate a learned representation122of a digital circuit design102. The neural network system100is an example of a system implemented as computer programs on one or more computers in one or more locations, in which the systems, components, and techniques described below can be implemented.

The neural network system100includes a graph generation system110, a graph neural network120, and a prediction neural network130.

The graph generation system110is configured to process data representing the digital circuit design102to generate a graph112that represents the digital circuit design102. The graph112can include (i) multiple nodes each representing a respective component of the digital circuit design, and (ii) multiple edges that each connect a respective pair of nodes and that each represent a connection between the respective components of the digital circuit design represented by the pair of nodes.

The graph neural network120is configured to process data representing the graph112to generate the learned representation122of the digital circuit design102. The learned representation122can include, for each component of the digital circuit design102represented by a respective node of the graph, an updated representation of the component generated by the graph neural network120.

The prediction neural network130is configured to process the learned representation122of the digital circuit design102to generate a prediction132about the digital circuit design. Example prediction tasks that can be performed using the learned representation122of the digital circuit design102are discussed below.

The digital circuit design102can be a design for any appropriate type of digital circuit. As a particular example, the digital circuit design102can be a design for a reduced instruction set computer (RISC) digital circuit, e.g., a digital circuit having a RISK-V architecture such as an IBEX digital circuit. In some implementations, the digital circuit design102represents a design for a special-purpose digital circuit, i.e., a digital circuit designed to execute a particular type of task. For example, the digital circuit can be designed specifically to execute machine learning tasks, e.g., the digital circuit can be a tensor processing unit (TPU) or a different ASIC that is designed to accelerate machine learning computations in hardware.

The neural network system100can be configured to receive any appropriate type of data that represents the digital circuit design102. For example, the neural network system100can receive the source code for a program that implements the digital circuit design102. For example, the source code can be written in a hardware description language, such as Verilog or VHSIC Hardware Description Language (VHDL). As another example, instead of or in addition to receiving source code representing the digital circuit design102, the neural network system100can receive data representing an abstract syntax tree (AST) of the source code. As another example, instead of or in addition to receiving the source code and/or the AST representing the digital circuit design102, the neural network system100can receive data representing a gate level netlist representing the digital circuit design102.

The data representing the digital circuit design102can be a representation at any appropriate abstraction level, e.g., the register-transfer level (RTL) or the gate level of abstraction.

In some implementations, the neural network system100can be configured to process data representing only a portion of a digital circuit design102and to generate a learned representation112of the portion of the digital circuit design102. For example, the neural network system100can be configured to generate a learned representation112of a strict subset of the modules of the digital circuit design102, or any appropriate subcircuit of the digital circuit design. Although the below description generally refers to generating learned representations of full digital circuit designs, it is to be understood that the same techniques can be applied to generate learned representations of respective portions of digital circuit designs, e.g., by generating graphs112representing the portions of the digital circuit designs.

As mentioned above, the graph generation system110is configured to process data representing the digital circuit design102to generate a graph112that represents the digital circuit design102.

For example, if the neural network system100is configured to receive data representing the digital circuit design102at the gate level, then the graph generation system110can process the data to generate a gate-level state transition graph112representing the digital circuit design102, where each node of the gate-level state transition graph112corresponds to single value of the bit-level state of the registers of the digital circuit design, and each edge of the gate-level state transition graph112represents a legal change in state that the digital circuit can make in a single clock cycle. That is, an edge between a first node and a second node representing respective values for the full state of the registers can represent a transition from the state represented by the first node to the state represented by the second node, where the digital circuit can change from the state represented by the first node to the state represented by the second node in a single clock cycle of the digital circuit.

As another example, if the neural network system100is configured to receive data representing the digital circuit design102at the register-transfer level (e.g., if the neural network system100receives RTL source code for the digital circuit design102), then the graph generation system110can process the data to generate a control data flow graph (CDFG)112representing the digital circuit design102.

Although the below description generally refers to generating a processing a graph112that is a CDFG representing the digital circuit design102at the register-transfer level, it is to be understood that the same techniques can be applied using any appropriate representation of the digital circuit design102.

One or more nodes of the graph112can represent one or more respective statements in the source code for the digital circuit design102. In some implementations, each node in the graph112represents one or more respective statements. That is, each node in the graph112can represent a single statement of the source code or a sequence of multiple statements of the source code, e.g., a particular path within the source code that would be traversed given a particular input to a digital circuit manufactured according to the digital circuit design102. In some other implementations, the graph112can include one or more nodes that do not represent statements of the source code representation of the digital circuit design102.

Although the below description generally refers to implementations in which each node of the graph112represents a single statement from the source code of the digital circuit design102, it is to be understood that the same techniques can be applied in implementations in which at least some nodes of the graph112represent multiple statements, e.g., multiple consecutive statements within the source code.

The graph112can include one or more edges, called “control” edges, that represent control flow between respective pairs of statements in the source code of the digital circuit design102. That is, a control edge from a first node to a second node represents a control flow between the statement represented by the first node and the statement represented by the second node, i.e., where the output of the statement represented by the first node can either trigger or not trigger the execution of the statement represented by the second node. Control edges are sometimes called “first” edges herein.

The graph112can include one or more edges, called “data” edges, that represent data flow between respective pairs of statements in the source code of the digital circuit design102. That is, a data edge from a first node to a second node represents a data flow between the statement represented by the first node to the statement represented by the second node, i.e., where a variable whose value is generated by the statement represented by the first node is used by the statement represented by the second node.

Typically, each edge in the graph112is a directed edge, i.e., encodes a directionality (e.g., a direction of control flow or data flow) from one “parent” node to another “child” node.

In some implementations, each edge in the graph112is either a control edge or a data edge. In some other implementations, the graph112can include one or more edges that do not represent either control flow or data flow within the source code representation of the digital circuit design102. For example, one or more edges of the graph112can encode information about the expected time taken to execute a respective statement in hardware, and/or one information about the expected power consumption of executing a respective statement in hardware.

The graph generation system110can generate an initial embedding for each node in the graph using data representing the statement of the source code of the digital circuit design102represented by the node. In this specification, an embedding is an ordered collection of numeric values that represents an input in a particular embedding space. For example, an embedding can be a vector of floating point or other numeric values that has a fixed dimensionality.

For example, for each node of the graph112, the graph generation system110can generate the initial embedding for the node from a set of attributes describing the statement represented by the node. The attributes can be provided to the neural network system100with the data representing the digital circuit design102, or the graph generation system110can determine the attributes by processing the data representing the digital circuit design102(e.g., by processing the source code). For example, the set of attributes can include one or more of: an identifier identifying the node (e.g., a unique numeric value assigned to the node); a node type of the node; fan-in data such as a number or type of parent nodes of the node; fan-out data such as a number or type of child nodes of the node; a condition represented by the node, e.g., if the node has the control node type described below; whether the node represents the start of an always block; an identification of a path in the graph121to which the node belongs; an identification of an assertion, property, or output that is influenced by the statement represented by the node; an identification of a pipeline stage of the statement represented by the node; or an identification of one or more signals on the sensitivity list of the statement represented by the node. As a particular example, the graph generation system can concatenate the set of attributes to generate an attribute vector, and determine the initial embedding to be the attribute vector or determine the initial embedding from the attribute vector.

As particular examples, the node types of respective nodes of the graph112can include one or more of: an operation node type, where nodes having the operation node type represent statements in the source code that process data, e.g., statements that represent arithmetic, logical, relational, or complex functions, or module instantiations; a control node type, where nodes having the control node type represent statements in the source code that are conditional decisions, e.g., branches, loops, or cases; or a storage node type, where nodes having the storage node type represent statements in the source code that instantiate or update variables or signals that are read from or written to by respective operations.

As another example, for each node of the graph112, the graph generation system110can generate the initial embedding for the node by processing the portion of the source code corresponding to the statement represented by the node. For example, the graph generation system110can identify a sequence of tokens representing the statement, e.g., where each token represents a word or character of the source code. The graph generation system110can combine the tokens in the sequence to generate a combined representation of the sequence of tokens, and determine the initial embedding to be the combined representation or determine the initial embedding from the combined representation.

As a particular example, the graph generation system110can determine the combined representation to be a mean of the tokens. As another particular example, the graph generation system110can determine the combined representation by processing the sequence of tokens using a pooling function, e.g., max pooling or mean pooling. As another particular example, the graph generation system110can generate the combined representation by processing the sequence of tokens using a recurrent neural network, e.g., a long short-term memory network (LSTM). That is, the graph generation system110can determine a combined representation ϕ(sn) for each node n by computing:

ϕ⁡(sn)=LSTM⁡(<s1n,s2n,…,skn>)where sn=, s1n, s2n, . . . , sknis the sequence of tokens representing the statement corresponding to the node.

In some implementations, for each node of the graph112, the graph generation system110can generate the initial embedding by combining, e.g., through concatenation, (i) the set of attributes of the statement corresponding to the node and (ii) the combined representation of the sequence of tokens representing the statement corresponding to the node. That is, the graph generation system can generate an initial embedding ϕ(0)(n) for each node n by computing

ϕ(0)(n)=Concat⁡(<ϕ⁡(sn),f1n,…,fln>)where each fjnis an attribute of the statement corresponding to the node.

An example graph representing a digital circuit design is discussed in more detail below with reference toFIG.2

In some implementations, an external system is configured to process the data representation the digital circuit design102to generate the graph112, and provide data representing the graph112to the neural network system100. That is, in some implementations, the neural network system100does not include the graph generation system110, but rather receives the graph112from an external system.

The graph neural network120can process the graph112to generate the learned representation122of the digital circuit design102. In particular, at each of multiple stages of the execution of the graph neural network120, the graph neural network120can update the respective embedding for each node of the graph112. Then, after the final stage, the graph neural network120can output a learned representation122of the digital circuit design that includes, for each node in the graph corresponding to a respective statement, a final embedding for the node (which can be considered an embedding of the statement). That is, the learned representation122can be wholly or partially composed of respective embeddings for each statement in the source code of the digital circuit design102.

That is, at each stage t of the graph neural network120, the current representation ψ(t)of the digital circuit102can be given by:

ψ(t)(G)={ϕ(t)(n)⁢❘"\[LeftBracketingBar]"∀n∈N}where G represents the graph112and N is the total number of nodes in the graph112.

At each stage t, the graph neural network120can update the current representation ψ(t)of the digital circuit102by computing:

Where fθrepresents the operations of the graph neural network120having learned network parameters θ.

The graph neural network120can have any appropriate configuration for updating the embeddings for the nodes of the graph112. Example graph neural networks that are configured to generate learned representations of digital circuit designs are discussed below with reference toFIG.2.

In some implementations, the graph neural network120determines to end execution after a predetermined number T of stages. In some other implementations, the graph neural network120determines, after each stage, whether to end execution according to whether one or more conditions have been satisfied. For example, after each stage t, the graph neural network120can determine a degree to which the current embeddings ϕ(t)(n) for the nodes n were updated during the stage, e.g., an average difference, across all nodes n, between ϕ(t-1)(n) and ϕ(t)(n). If the average difference is below a predetermined threshold, then the graph neural network120can determine to end execution and output the current representation ψ(t)of the digital circuit102as the final learned representation122.

As mentioned above, the prediction neural network130can process the learned representation122of the digital circuit design to generate a prediction132about the digital circuit design102.

In some implementations, after the graph neural network120generates the learned representation122of the digital circuit design102, the neural network system100provides the learned representation122directly to the prediction neural network130.

In some other implementations, after the graph neural network120generates the learned representation122of the digital circuit design102, the neural network system100stores the learned representation122in a data store for later use. Then, at a future time, the prediction neural network130can obtain the learned representation112from the data store and process the learned representation122to generate the prediction132. That is, although the graph neural network120is depicted inFIG.1as providing the learned representation122directly to the prediction neural network130, in some implementations the graph neural network120and the prediction neural network130can execute asynchronously. For example, at a first time point the neural network system100can generate the learned representation122of the digital circuit design102, and then at multiple future time points a respective prediction neural network can use the learned representation122to generate a prediction132about the digital circuit design102.

In some implementations, the learned representation122can be used by multiple different prediction neural networks130that are each configured to perform a respective different machine learning task using the learned representation122. That is, the graph neural network120can be configured through training to encode information about the digital circuit design102into the learned representation122that can be leveraged to perform multiple different prediction tasks.

The prediction neural network130can be configured through training to generate any appropriate prediction130about the digital circuit design102. For example, the prediction neural network130can be configured to detect bugs in the digital circuit design102; as a particular example, the prediction132can include an identification of one or more statements or blocks of statements in the digital circuit design102that are likely to execute differently than intended. As another example, the prediction132can include data characterizing one or more desirable properties or assertions of the digital circuit design102; as a particular example, the prediction neural network130can be configured to perform formal verification on the digital circuit design102.

As another example, the prediction neural network130can be configured to perform hardware verification of the digital circuit design102, e.g. as part of an industrial hardware design cycle. That is, the prediction132about the digital circuit design102can be a prediction of whether a particular test input to a digital circuit manufactured according to the digital circuit design102will cause a particular coverage point to be covered. A coverage point (or simply cover point) is a sequence of statements of the source code of the digital circuit design102(or, equivalently, a sequence of nodes in the graph112). If a particular test input to the digital circuit design102causes each statement in the sequence to be executed, then the particular test input is said to “cover” the coverage point. In this example, the network input for the prediction neural network130can include (i) the learned representation122of the digital circuit design102, (ii) an identification of the coverage point and (ii) an identification of a test input.

Example techniques for performing verification using a learned representation of a digital circuit design are discussed in more detail below with reference toFIG.4.

As another example, the prediction neural network130can be configured to generate a new test input that is predicted to cover a particular desired coverage point (or a set of multiple desired coverage points).

Example techniques for generating new test inputs using a learned representation of a digital circuit design are discussed in more detail below with reference toFIG.5.

In other words, the neural network system100can be a component of a software that is configured to perform verification of digital circuit designs. That is, users can generate new designs for digital circuits and use the software to verify whether the design satisfies a set of requirements. For example, the neural network system100can be made available to digital circuit engineers or other users through an application programming interface (API), or can be a portion of a software application that runs on a user device.

As another example, the prediction neural network130can be configured to predict, given a particular test input (or distribution over test inputs), respective values that one or more variables will have after a digital circuit manufactured according to the digital circuit design102processes the particular test input. As another example, the prediction neural network130can be configured to generate constraints for test inputs that are predicted to cover particular desired coverage points.

The graph neural network120and the prediction neural network130can be trained using any appropriate technique.

In some implementations, the graph neural network120and the prediction neural network130are trained concurrently, end-to-end. For example, a training system can process, from a training data set of training digital circuit designs, a training digital circuit design to using the neural network system100to generate a prediction about the training digital circuit design. The training system can determine an error in the prediction about the training digital circuit design, and backpropagate the error through both the prediction neural network130and the graph neural network120to determine a parameter update to the network parameters of the neural networks130and120, e.g., using gradient descent. In some implementations in which the graph generation system110includes one or more neural network layers (e.g., the recurrent neural network layers configured to generate the initial representation for each node in the graph112as described above), the training system can further train the neural network layers of the graph generation system110concurrently with the graph neural network120and the prediction neural network130.

In some other implementations, a training system first trains the graph neural network120using a first prediction task (e.g., the verification or test generation tasks described above) to determine trained values for the network parameters of the graph neural network120(and, optionally, any neural network layers in the graph generation system110). The training system can then use the trained graph neural network120to generate learned representations122, and use the learned representations to train the prediction neural network130on a second prediction task to determine trained values for the network parameters of the prediction neural network130(optionally fine-tuning, i.e., updating, the values for the network parameters of the graph neural network120).

The training system can train one or more of the graph neural network120or the prediction neural network130using training examples that include (i) training digital circuit designs and (ii) ground-truth outputs for a particular prediction task, e.g., coverage information describing how respective coverage points of the training digital circuit designs are covered. For example, for each training digital circuit design, the training system can generate one or more random test inputs and, for each test input, use a simulator (e.g., a Verilog simulator) to generate ground-truth labels of whether a particular coverage point is covered by the test input.

The training system can use any appropriate loss function. As a particular example, the training system can determine the errors in the predictions generated by the neural network system100during training using a binary cross entropy loss function.

A user of the neural network system100, e.g., an engineer working on designing a new digital circuit, can thus provide different respective designs102for the new digital circuit to the neural network system100for analysis. For example, the user can use the neural network system100to predict whether a particular design appropriately covers a particular coverage point. In response to a prediction132generated the prediction neural network130, the user (or an external automated system) can determine to update the design102of the new digital circuit. For example, the user can determine, in response to the prediction neural network130predicting that a particular coverage point cannot be covered using any test input, to update the design102of the new digital circuit so that the updated design102can cover the particular coverage point for a certain test input. As another example, an automated system can be configured to repeatedly send designs102to the neural network system100and, if the prediction neural network130generates a prediction that the current design102fails one or more criteria, update the design102, e.g., using an evolutionary technique that incrementally updates the design102, e.g., according to one or more predetermined heuristics.

After determining, according to the predictions132generated by the prediction neural network130, that a particular design102satisfies all criteria, the user or external system can determine to finalize the digital circuit design102. The finalized digital circuit design102can then be provided to a manufacturing system for manufacturing digital circuits according to the design102, i.e., manufacturing digital circuits that have an architecture defined by the design102. The manufactured digital circuits can then be deployed on respective electronic devices, e.g., on cloud computing hardware or on user devices such as mobile phones or laptops.

FIG.2illustrates an example graph200determined from a digital circuit design.

For example, the graph200can be generated by a graph generation system of a neural network system configured to generate learned representations of digital circuit designs, e.g., the graph generation system110of the neural network system100described above with reference toFIG.1.

The graph200can be generated from source code that implements the digital circuit design, e.g., source code written in a hardware description language as described above.

The graph200includes (i) a set of nodes210a-lthat each represent a respective statement of the source code of the digital circuit design, (ii) a set of control edges220a-1(depicted as solid lines inFIG.2) that each represent a control flow between respective statements, and (iii) a set of data edges230a-b(depicted as dashed lines inFIG.2) that each represent a data flow between respective statements.

The graph200includes three sub-graphs202,204, and206that each represent a respective block of statements of the source code of the digital circuit design. In particular, the sub-graphs202,204, and206each represent “always” blocks that repeatedly execute when a digital circuit manufactured using the digital circuit design executes.

The always blocks represented by the sub-graphs202,204, and206can execute in parallel. In particular, at each clock cycle of the execution of the digital circuit, an external clock signal can trigger, for each always block, execution of a respective statement. The statements in each always block are therefore executed in sequence over multiple consecutive clock cycles. When executing a statement, the input values of respective variables of the digital circuit in the current cycle come from the output values of the respective variables from the previous cycle.

For each sub-graph202,204, and206of the graph200, the graph200can include an control edge from the final node in the sub-graph (i.e., node210din the first sub-graph202, node210hin the second sub-graph204, and node210lin the third sub-graph206) to the first node in the sub-graph (i.e., node210ain the first sub-graph202, node210ein the second sub-graph204, and node210iin the third sub-graph206), representing the cyclic execution of the always blocks.

The source code corresponding to the nodes of the sub-graph202is reproduced below:

The first node210ain the sub-graph202represents the “if” statement.

If the variable c is greater than the variable d, then the control edge220ais followed to the node210b, and the statement corresponding to the node210bis executed. The control edge220cis then followed to the final node210din the sub-graph202, which represents the end of the always block.

If the variable c is not greater than the variable d, then the control edge220bis followed to the node210c, and the statement corresponding to the node210cis executed. The control edge220dis then followed to the final node210din the sub-graph202.

The source code corresponding to the nodes of the sub-graph204is reproduced below:

The first node210ein the sub-graph204represents the “if” statement.

If the variable c is equal to the variable d, then the control edge220eis followed to the node210f, and the statement corresponding to the node210fis executed. The control edge220gis then followed to the final node210hin the sub-graph204, which represents the end of the always block.

If the variable c is not equal to the variable d, then the control edge220fis followed to the node210g, and the statement corresponding to the node210gis executed. The control edge220his then followed to the final node210din the sub-graph204.

The source code corresponding to the nodes of the sub-graph206is reproduced below:

The first node210iin the sub-graph206represents the “if” statement. Because the “if” statement depends on the values of the variables a and b, which are generated by respective nodes of the sub-graphs202and204, the graph200includes a data edge230abetween the final node210dof the sub-graph202to the first node210iof the sub-graph206, and a data edge230bbetween the final node210hof the sub-graph204and the first node210iof the sub-graph206.

If the variable a is greater than the variable b, then the control edge220iis followed to the node210j, and the statement corresponding to the node210jis executed; namely a state variable of the digital circuit is set to “active.” The control edge220kis then followed to the final node210lin the sub-graph206, which represents the end of the always block.

If the variable a is not greater than the variable b, then the control edge220jis followed to the node210k, and the statement corresponding to the node210kis executed; namely, the state variable of the digital circuit is set to “idle.” The control edge220lis then followed to the final node210lin the sub-graph206.

Respective embeddings for each of the nodes210a-lcan be updated by a graph neural network at each of multiple stages to generate a learned representation of the digital circuit design that includes respective final embeddings for each of the nodes210a-l. For example, the graph neural network120described above with reference toFIG.1can process data representing the graph200to generate a learned representation of the digital circuit design.

The graph neural network configured to process the graph200can have any appropriate configuration. For example, the graph neural network can be a graph convolutional network (GCN), e.g., as described in “Semi-Supervised Classification with Graph Convolutional Networks,” Kipf et al., arxiv: 1609.02907. As another example, the graph neural network can be a gated graph neural network, e.g., as described in “Gated Graph Sequence Neural Networks,” Li et al., arXiv: 1511.05493. As another example, the graph neural network can be a graph neural network multilayer perception (GNN-MLP), e.g., as described in “GNN-FiLM: Graph Neural Networks with Feature-wise Linear Modulation,” Marc Brockschmidt, arXiv: 1906.12192.

As another example, the graph neural network can be an instruction pointer attention graph neural network (IPA-GNN), e.g., as described in “Learning to Execute Programs with Instruction Pointer Attention Graph Neural Networks,” Bieber et al., arXiv: 2010.12621, the entire contents of which are hereby incorporated by reference.

In some implementations in which the graph neural network is an IPA-GNN, the graph neural network can maintain multiple different instruction pointers (instead of a single instruction pointer), e.g., a respective instruction pointer for each “always” block in the source code of the digital circuit design. For example, before the first stage, the graph neural network120can instantiate a soft instruction pointer pt,nas:

At each stage t, the graph neural network120can compute a hidden state proposal as:

ai,n(1)=Dense(ht-1,n)where “Dense” represents a sequence of one or more feedforward neural network layers.

In some implementations in which the graph neural network120is an IPA-GNN, the graph neural network can process graphs generated from digital circuit designs that include switch statements (instead of only binary conditions). For example, at each stage t, the graph neural network can compute a soft branch decision as:

bt,n,m=softmax(Dense(ht-1,n)·Embed(en,m))where m∈Nout(xn) is a control node child of node xn, i.e., a child of node xnvia a control edge; and Embed(en,m) is an embedding for the control edge from xnto xm. The embedding can include or be generated from one or more of: an embedding of whether the condition is positive or negative, a first variable referenced by the condition, or a form of the condition.

In some implementations in which the graph neural network is an IPA-GNN, the graph neural network can model the propagation of messages between nodes (corresponding to respective statements) along data edges at each stage t. For example, the graph neural network can determine, for each particular node, a hidden state proposal from one or more of (i) control node state proposals (e.g., from nodes that are within the particular node's always block) or (ii) proposals of other parent nodes (e.g., from nodes that are in a different always block). As a particular example, the graph neural network can compute the hidden state proposal for each node n at stage t as:

ht,n′=∑n′∈Nm(n)⋂Nctrlpl-1,n′·bt,n′,n·at,n′(1)+∑n′∈Nio(n)⋂N_ctrlai,n′(1)where Nctrl⊆N identifies the set of control nodes in the graph.

In some implementations in which the graph neural network is an IPA-GNN, the graph can include an explicit or implicit edge, for each always blocks, from (i) the final (or “sink”) node in the always blocks and (ii) the first (or “root”) node in the always block, thus modelling non-termination.

FIG.3is a flow diagram of an example process300for generating a learned representation of a digital circuit design. For convenience, the process300will be described as being performed by a system of one or more computers located in one or more locations. For example, a neural network system, e.g., the neural network system100described above with reference to inFIG.1, appropriately programmed in accordance with this specification, can perform the process300.

The system obtains data representing a program that implements the digital circuit design (step302). The program can include a set of multiple statements.

The system processes the obtained data to generate data representing a graph representing the digital circuit design (step304). The graph can include: (i) a set of multiple nodes representing respective statements of the program, (ii) a set of multiple first edges (i.e., control edges), and (iii) a set of multiple second edges (i.e., data edges). Each first edge is between a respective pair of nodes of the set of nodes and represents a control flow between a pair of statements of the program that are represented by the respective pair of nodes. Each second edge is between a respective pair of nodes of the set of nodes and represents a data flow between a pair of statements of the program that are represented by the respective pair of nodes.

The system generates the learned representation of the digital circuit design using the graph (step306). In particular, the system can process the data representing the graph using a graph neural network to generate a respective learned representation of each statement represented by a node of the graph. Collectively, the learned representations of the statements can represent the learned representation of the digital circuit design.

FIG.4is a flow diagram of an example process400for using a learned representations of a digital circuit design to predict coverage. For convenience, the process400will be described as being performed by a system of one or more computers located in one or more locations. For example, a neural network system, e.g., the neural network system100described above with reference to inFIG.1, appropriately programmed in accordance with this specification, can perform the process400.

In particular, the system can generate a prediction of whether a particular coverage point will be covered by a digital circuit manufactured according to the digital circuit design in response to processing a particular test input.

The particular coverage point includes a sequence of one or more statements of a source code that implements the digital circuit design.

The particular test input can identify, for each of one or more variables of the digital circuit design, a particular value or range of values for the variable. Each variable can, e.g., be a Boolean variable, an integer variable, or a categorical variable.

The system obtains a learned representation of a digital circuit design (step402). The learned representation can be generated by a graph neural network of the neural network system in response to processing a graph representing the digital circuit design, e.g., the graph neural network120described above with reference toFIG.1.

The system generates a network input from (i) the learned representation of the digital circuit design, (ii) an identification of the particular cover point, and (iii) an identification of the particular test input (step404).

For example, the system can generate a first network input from the learned representation that represents the coverage point. As described above learned representation of the digital circuit design can include a respective learned representation of each statement in the source code of the digital circuit design. Thus, the first network input can be generated from the learned representations of the statements in the particular coverage point.

For example, the system can generate a bitmask that is to be applied to the complete set of learned representations of respective statements, where the bitmask masks (i.e., removes) all learned representations in the set except for the learned representations of the statements of the coverage point. The system can apply the generated bitmask to identify the statements of the particular coverage point C:

C=<n1,n2,…,nm>where m is the number of statements in the particular coverage point and each nirepresents the ithstatement in the particular coverage point.

The system can process the respective learned representations of the statements in C to generate the first network input. For example, the system can determine the first network to be a concatenation or sum of the m learned representations ϕ(ni). As another example, the system can process the m learned representations ϕ(ni) using one or more recurrent neural network layers, e.g., LSTM neural network layers, to generate the first network input. That is, the system can compute the first network input ϕ(T)(C) to be:

The system can also generate a second network input that represents the particular test input. For example, the system can determine a concatenation of the j respective values ijfor the parameters I of the particular test input, and process the concatenated values using one or more neural network layers, e.g., using one or more feedforward neural network layers. That is, the system can compute the second network input ϕ(I) to be:

The system can then generate the network input by combining the first network input and the second network input, e.g., by determining a sum or concatenation of the first network input and the second network input.

The neural network layers used to generate the network input can be considered to be a component of the prediction neural network described below.

The system processes the network input using a prediction neural network to generate a prediction of whether the particular test input to the digital circuit manufactured according to the digital circuit design will cause the particular coverage point to be covered (step406). For example, the prediction neural network can be the prediction neural network130described above with reference toFIG.1.

For example, the output of the prediction neural network can be a likelihood value, e.g., a value between 0 and 1, that represents a likelihood that the test would cover the coverage point.

As a particular example, the prediction neural network can include one or more feedforward neural network layers. That is, the system can compute:

FIG.5is a flow diagram of an example process500for using a learned representations of a digital circuit design to generate new test inputs. For convenience, the process500will be described as being performed by a system of one or more computers located in one or more locations. For example, a neural network system, e.g., the neural network system100described above with reference to inFIG.1, appropriately programmed in accordance with this specification, can perform the process500.

In particular, the system can generate a new test input that is predicted to provide coverage of a particular coverage point in a digital circuit manufactured according to the digital circuit design.

The particular coverage point includes a sequence of one or more statements of a source code that implements the digital circuit design.

The new test input can identify, for each of one or more variables of the digital circuit design, a particular value or range of values for the variable. Each variable can, e.g., be a Boolean variable, an integer variable, or a categorical variable.

The system can generate the new test input using gradient search. The system can perform the gradient search using a prediction neural network that has been pre-trained on a different prediction task, e.g., the coverage prediction task described above with reference toFIG.1andFIG.4. That is, the same prediction neural network can be configured to perform both the process500and the process400described above with reference toFIG.4.

The system obtains a learned representation of a digital circuit design (step502). The learned representation can be generated by a graph neural network of the neural network system in response to processing a graph representing the digital circuit design, e.g., the graph neural network120described above with reference toFIG.1.

The system generates an initial test input for covering the particular coverage point (step504). For example, the system can randomly generate the initial test input. As another example, the system can select an initial test input that is known (e.g., from previous executions of the prediction neural network) to cover a different coverage point that is similar to or local to the particular coverage point (e.g., another coverage point in the same block of the source code that implements the digital circuit design).

The system processes a network input generated from the initial test input and the particular coverage point using the prediction neural network to generate a prediction of whether the initial test input to the digital circuit manufactured according to the digital circuit design will cause the particular coverage point to be covered (step506). For example, the network input can be generated from the initial test input and the particular coverage point as described above with reference toFIG.4.

For example, the output of the prediction neural network can be a likelihood value, e.g., a value between 0 and 1, that represents a likelihood that the test would cover the coverage point.

The system updates the initial test input according to the prediction generated by the prediction neural network (step508). In particular, the system can determine a difference between the generated prediction and a “desired” prediction that indicates the initial test would cover the coverage point. For example, if the prediction neural network is configured to generate a likelihood value as described above, then the desired prediction can be an output of 1.

The goal of the system is to identify a new test input that, when a corresponding network input is processed by the prediction neural network, causes the prediction neural network to output the desired prediction that the test would cover the particular coverage point (e.g., causes the prediction neural network to generate an output of 1).

The system can treat the determined difference as an “error” of the prediction neural network, and backpropagate the difference through the prediction neural network. However, instead of updating the parameter values of the prediction neural network, the system can leave the parameter values constant and update the component of the network input representing the initial test (e.g., the second network input described above with reference toFIG.4). For example, the system can update the component of the network input that represents the initial test using gradient descent or gradient ascent to generate an updated network input.

The updated network input represents an updated test input that is closer to covering the particular coverage point than the initial test. The system can recover the updated test input from the updated network input. For example, in implementations in which the updated network input is a concatenation of (i) a first network input representation the particular coverage point and (ii) a second network input representing the updated test input, as described above with reference toFIG.4, the system can remove the first network input from the concatenation to recover the second network input. The remaining second network input can then include a respective value for each parameter of the updated test input, as described above with reference toFIG.4.

The system can repeat steps506and508multiple times to repeatedly update the current test input until identifying a new test input that is predicted to successfully cover the particular coverage point. For example, the system can repeat steps506and508until the likelihood value generated by the prediction neural network is greater than a threshold value, e.g., 0.5, 0.9, or 0.99.

Embodiment 1 is a method of generating a learned representation of a digital circuit design, the method comprising:obtaining data representing a program that implements the digital circuit design, the program comprising a plurality of statements;processing the obtained data to generate data representing a graph representing the digital circuit design, the graph comprising:a plurality of nodes representing respective statements of the program,a plurality of first edges, wherein each first edge is between a respective pair of nodes of the plurality of nodes and represents a control flow between a pair of statements of the program that are represented by the respective pair of nodes, anda plurality of second edges, wherein each second edge is between a respective pair of nodes of the plurality of nodes and represents a data flow between a pair of statements of the program that are represented by the respective pair of nodes; andgenerating the learned representation of the digital circuit design, comprising processing the data representing the graph using a graph neural network to generate a respective learned representation of each statement represented by a node of the graph.

Embodiment 2 is the method of embodiment 1, further comprising:processing, using a prediction neural network, a network input generated from the learned representation of the digital circuit design to generate a prediction about the digital circuit design.

Embodiment 3 is the method of embodiment 2, wherein the prediction is directed to a verification task of the digital circuit design.

Embodiment 4 is the method of embodiment 3, wherein the prediction about the digital circuit design comprises a prediction of whether a particular input to a digital circuit manufactured according to the digital circuit design will cause a particular coverage point to be covered.

Embodiment 5 is the method of embodiment 4, wherein the network input comprises:a first network input representing the particular coverage point, anda second network input representing the particular test.

Embodiment 6 is the method of embodiment 5, wherein processing, using the prediction neural network, the network input to generate the prediction comprises:concatenating the first network input and the second network input to generate a concatenated network input; andprocessing the concatenated network input using one or more feedforward neural network layers.

Embodiment 7 is the method of any one of embodiments 5 or 6, wherein:the particular coverage point is defined by a subset of the plurality of statements; andthe first network input has been generated by performing operations comprising:obtaining the respective learned representation of each statement in the subset, andcombining the obtained learned representations to generate the first network input.

Embodiment 8 is the method of embodiment 7, wherein obtaining the respective learned representation of each statement in the subset comprises:obtaining representation data characterizing the respective learned representation for each statement of the plurality of statements;generating a bitmask for the representation data, wherein the bitmask masks out each learned representation except for the respective learned representations of each statement in the subset; andapplying the bitmask to the representation data.

Embodiment 9 is the method of any one of embodiments 7 or 8, wherein combining the obtained learned representations comprises processing the obtained learned representations using a recurrent neural network.

Embodiment 10 is the method of any one of embodiments 5-9, wherein the second network input has been generated by performing operations comprising:obtaining second data characterizing the particular test, the second data comprising a respective value for each of a plurality of predetermined variables of the particular test; andprocessing the second data using one or more feedforward neural network layers.

Embodiment 11 is the method of any one of embodiments 2-10, wherein the prediction about the digital circuit design comprises an identity of a new test that is predicted to cover a desired coverage point.

Embodiment 12 is the method of embodiment 11, wherein the new test has been generated by performing operations comprising:processing, using the prediction neural network, an initial network input characterizing an initial test;determining, using a network output generated by the prediction neural network in response to processing the initial network input, whether the initial test would cover the desired coverage point;determining a difference between (i) the network output and (ii) a desired network output that indicates that the initial test would cover the desired coverage point; andbackpropagating the determined difference through the prediction neural network to determine an update to the initial network input.

Embodiment 13 is the method of any one of embodiments 1-12, further comprising generating, for each node in the graph that represents a statement, an initial embedding for the node, comprising:obtaining third data characterizing a plurality of attributes of the node;obtaining a sequence of tokens representing the statement represented by the node; andprocessing (i) the third data and (ii) the sequence of tokens to generate the initial embedding for the node.

Embodiment 14 is the method of embodiment 13, wherein processing (i) the third data and (ii) the sequence of tokens to generate the initial embedding for the node comprises:processing the sequence of tokens using a recurrent neural network to generate a combined representation of the sequence; andconcatenating (i) the combined representation of the sequence and (ii) the third data to generate the initial embedding.

Embodiment 15 is a system comprising one or more computers and one or more storage devices storing instructions that when executed by the one or more computers cause the one more computers to perform the operations of the respective method of any one of embodiments 1-14.

Embodiment 16 is one or more computer storage media storing instructions that when executed by one or more computers cause the one more computers to perform the operations of the respective method of any one of embodiments 1-14.