Inter-kernel dataflow analysis and deadlock detection
Inter-kernel dataflow analysis and deadlock detection includes, for each kernel of a plurality of kernels of a design, including, using computer hardware, a signal for the kernel that is asserted in response to all processes inside the kernel stalling, wherein the plurality of kernels form a strongly connected component. For each kernel of the plurality of kernels, the signal is asserted during operation of the design in response to each process in the kernel stalling. A notification is generated indicating that the strongly connected component is deadlocked in response to each kernel of the strongly connected component asserting the signal.
1 . A method, comprising:
for each kernel of a plurality of kernels of a design, including, using computer hardware, a signal in the kernel that is asserted in response to all processes inside the kernel stalling;
performing a first simulation of the design using an executable model of the design where a size of each of a plurality of First-In-First-Out (FIFO) channels of the design is permitted to grow according to data carried by each FIFO channel based on reads and writes to the FIFO channel;
for each kernel of the plurality of kernels, asserting the signal during the first simulation in response to each process in the kernel stalling;
detecting a data rate mismatch for a selected FIFO channel of the plurality of FIFO channels during the first simulation in response to detecting a rate of growth in size of the selected FIFO channel that exceeds a minimum predetermined rate; and
generating a notification indicating the data rate mismatch based on the detecting.
2 . The method of claim 1 , further comprising:
determining a maximum depth for one or more other FIFO channels of the plurality of FIFO channels of the design during the first simulation.
3 . The method of claim 2 , further comprising:
generating a hardware description language (HDL) version of the design.
4 . The method of claim 3 , further comprising:
performing second simulation of the HDL version of the design and, during the second simulation, monitoring for a deadlock, wherein depths of the plurality of FIFO channels of the design are set to maximum depths determined during the first simulation; and
outputting a further notification indicating whether a depth of the FIFO channels is adequate based on whether a deadlock is detected during the second simulation.
5 . The method of claim 4 , wherein, in response to detecting the deadlock during the second simulation, the notification indicates that a source of the deadlock is an error by a high-level synthesis tool in generating the HDL version of the design.
6 . The method of claim 1 , further comprising:
for each kernel of the plurality of kernels, generating blocking status data specifying which FIFO channels of an interface of the kernel are blocked during operation;
for a kernel stream graph specifying connections between the plurality of kernels, updating, using computer hardware, the kernel stream graph based on the blocking status data for the plurality of kernels; and
in response to detecting a cycle in the kernel stream graph as updated, generating, using the computer hardware, a notification specifying which of the plurality of FIFO channels are involved in a deadlock.
7 . The method of claim 6 , wherein the updating includes the computer hardware adding edges to the kernel stream graph corresponding to blockages specified by the blocking status data.
8 . The method of claim 6 , wherein each kernel of the plurality of kernels includes a blocking matrix configured to store the blocking status data of the kernel, wherein each blocking matrix specifies a blocking status for each pair of FIFO channels of the kernel bidirectionally for each pair.
9 . A system, comprising:
a processor configured to initiate operations including:
for each kernel of a plurality of kernels of a design, including a signal in the kernel that is asserted in response to all processes inside the kernel stalling;
performing a first simulation of the design using an executable model of the design where a size of each of a plurality of First-In-First-Out (FIFO) channels of the design is permitted to grow according to data carried by each FIFO channel based on reads and writes to the FIFO channel;
for each kernel of the plurality of kernels, asserting the signal during the first simulation in response to each process in the kernel stalling;
detecting a data rate mismatch of a selected FIFO channel of the plurality of FIFO channels during the first simulation in response to detecting a rate of growth in size of the selected FIFO channel that exceeds a minimum predetermined rate; and
generating a notification indicating the data rate mismatch based on the detecting.
10 . The system of claim 9 , wherein the processor is configured to initiate executable operations including:
determining a maximum depth for each of the plurality of FIFO channels of the design during the first simulation;
generating a hardware description language (HDL) version of the design;
performing second simulation of the HDL version of the design and, during the second simulation, monitoring for a deadlock, wherein depths of the plurality of FIFO channels of the design set to the maximum depths determined during the first simulation; and
outputting a further notification indicating whether a depth of the plurality of FIFO channels is adequate based on whether a deadlock is detected during the second simulation.
11 . The system of claim 9 , wherein the processor is configured to initiate executable operations including:
for each kernel of the plurality of kernels, generating blocking status data specifying which FIFO channels of an interface of the kernel are blocked during operation;
for a kernel stream graph specifying connections between the plurality of kernels, updating the kernel stream graph based on the blocking status data for the plurality of kernels; and
in response to detecting a cycle in the kernel stream graph as updated, generating a notification specifying which FIFO channels of the plurality of kernels are involved in a deadlock.
12 . A method, comprising:
for each kernel of a plurality of kernels of a design, including, using computer hardware, a signal in the kernel that is asserted in response to all processes inside the kernel stalling;
performing a first simulation of the design using an executable model of the design where a size of each of a plurality of First-In-First-Out (FIFO) channels of the design is permitted to grow according to data carried by each FIFO channel based on reads and writes to the FIFO channel;
for each kernel of the plurality of kernels, asserting the signal during the first simulation in response to each process in the kernel stalling;
detecting a data rate mismatch for a selected FIFO channel of the plurality of FIFO channels based, at least in part, on whether a size of the selected FIFO channel stabilizes during the first simulation to a particular maximum size;
for each kernel of the plurality of kernels, generating blocking status data specifying which FIFO channels of an interface of the kernel are blocked during operation;
for a kernel stream graph specifying connections between the plurality of kernels, updating, using computer hardware, the kernel stream graph based on the blocking status data for the plurality of kernels; and
in response to detecting a cycle in the kernel stream graph as updated, generating, using the computer hardware, a notification specifying which of the plurality of FIFO channels are involved in a deadlock, wherein each kernel of the plurality of kernels includes a blocking matrix configured to store the blocking status data of the kernel, and wherein each blocking matrix specifies a blocking status for each pair of FIFO channels of the kernel bidirectionally for each pair.
13 . The method of claim 12 , further comprising:
determining a maximum depth for one or more other FIFO channels of the plurality of FIFO channels of the design during the first simulation.
14 . The method of claim 13 , further comprising:
generating a hardware description language (HDL) version of the design.
15 . The method of claim 14 , further comprising:
performing second simulation of the HDL version of the design and, during the second simulation, monitoring for a deadlock, wherein depths of the plurality of FIFO channels of the design are set to maximum depths determined during the first simulation; and
outputting a further notification indicating whether a depth of the FIFO channels is adequate based on whether a deadlock is detected during the second simulation.
16 . The method of claim 15 , wherein, in response to detecting the deadlock during the second simulation, the notification indicates that a source of the deadlock is an error by a high-level synthesis tool in generating the HDL version of the design.