Channel sizing for inter-kernel communication

Patent metadata

Field	Value
Publication number	US-2016378441-A1
Application number	US-201514749379-A
Country	US
Kind code	A1
Filing date	Jun 24, 2015
Priority date	Jun 24, 2015
Publication date	Dec 29, 2016
Grant date	—

Abstract

Systems and methods for dynamically sizing inter-kernel communication channels implemented on an integrated circuit (IC) are provided. Implementation characteristics of the channels, predication, and kernel scheduling imbalances may factor into properly sizing the channels for self-synchronization, resulting in optimized steady-state throughput.

First claim

What is claimed is:

1 . A tangible, non-transitory, machine-readable-medium, comprising machine readable instructions to:
convert a high level program into a low level program, wherein the low level program comprises a first kernel, a second kernel, and an inter-kernel channel that enables inter-channel communication between the first kernel and the second kernel; size the inter-kernel channel based upon one or more program implementation factors, predication factors, kernel scheduling imbalance factors, or any combination thereof; and provide the low level program to an integrated circuit for implementation on the integrated circuit.

2 . The machine-readable-medium of claim 1 , wherein the instructions to size the inter-kernel channel comprise instructions to:
size the inter-kernel channel based upon a latency of the inter-kernel channel.

3 . The machine-readable-medium of claim 2 , wherein the instructions to size the inter-kernel channel comprise instructions to:
size the inter-kernel channel, such that a minimum depth of the inter-kernel channel is greater than the latency of the inter-kernel channel.

4 . The machine-readable-medium of claim 1 , wherein the instructions to size the inter-kernel channel comprise instructions to:
size the inter-kernel channel based upon predication of the inter-kernel channel reads, writes, or both.

5 . The machine-readable-medium of claim 4 , wherein the instructions to size the inter-kernel channel comprise instructions to:
size the inter-kernel channel, such that a capacity of the inter-kernel channel is equal to or greater than an initial capacity of the inter-kernel channel plus a latency of the inter-kernel channel.

6 . The machine-readable-medium of claim 1 , wherein the instructions to size the inter-kernel channel comprise instructions to:
size the inter-kernel channel based upon scheduling imbalances between the first kernel and the second kernel.

7 . The machine-readable-medium of claim 6 , wherein the instructions to size the inter-kernel channel comprise instructions to:
construct an integer linear programming problem to size the inter-kernel channel.

8 . The machine-readable-medium of claim 7 , wherein the instructions to construct the integer linear programming problem comprise instructions to:
determine a maximum latency to reach a read portion of the inter-kernel channel (hereinafter max_latency(read)); determine a maximum latency to reach a write portion of the inter-kernel channel (hereinafter max_latency(write)); determine a minimum capacity that can be live prior to a read at the inter-kernel channel (hereinafter min_capacity(read)); determine a minimum capacity that can be live prior to a write to a kernel from the inter-kernel channel (hereinafter min_capacity(write)); determine a first kernel scheduling slack variable, the first kernel slack variable representing a delayed start of the first kernel relative to the second kernel; determine a second kernel scheduling slack variable, the second kernel slack variable representing a delayed start of the second kernel relative to the first kernel; apply a constraint for the inter-kernel channel, such that a slack variable from the first kernel scheduling slack variable or the second kernel scheduling slack variable corresponding to a reading kernel minus a slack variable from the first kernel scheduling slack variable or the second kernel scheduling slack variable corresponding to a writing kernel is greater than or equal to the max_latency(read) minus the min_capacity(write); define and minimize a cost function for the first kernel and the second kernel, wherein the cost function for the first kernel and the second kernel is defined as a sum of widths of all inter-channel kernels having a read in the respective first kernel or second kernel minus a sum of all inter-kernel channels having a write in the respective first kernel or second kernel; and set a depth of the inter-kernel channel to equal to the slack variable for the reading kernel minus the slack variable for the writing kernel plus max_latency(read) minus min_capacity(write).

9 . The machine-readable-medium of claim 1 , wherein the instructions to size the inter-kernel channel comprise instructions to:
size the inter-kernel channel based upon at least two of: a latency of the inter-kernel channel, predication, and scheduling imbalances of the first and second kernels.

10 . The machine-readable-medium of claim 1 , wherein the low level program comprises a plurality of inter-kernel channels, and the machine readable instructions comprise instructions to size two or more of the plurality of inter-kennel channels sizing, based upon a latency of a respective inter-kernel channel being sized, predication of the respective inter-kernel channel being sized, scheduling imbalances between kernels at endpoints of the respective inter-kernel channel being sized, or any combination thereof.

11 . An integrated circuit (IC) device comprising:
programmable logic comprising an implementation of one or more inter-kernel channels, wherein at least a subset of the one or more inter-kernel channels was sized by a compiler or programmable logic design software, based upon one or more program implementation factors, predication factors, kernel scheduling imbalance factors, or any combination thereof.

12 . The IC device of claim 11 , wherein the programmable logic comprises at least one partial reconfiguration (PR) block comprising a physical location on the IC that can be reconfigured during runtime of the IC.

13 . The IC device of claim 11 , wherein at least a subset of the one or more inter-kernel channels comprise a first-in-first-out (FIFO) buffer.

14 . The IC device of claim 11 , wherein the at least a subset of the one or more inter-kernel channels is sized based upon a latency of a respective inter-kernel channel being sized.

15 . The IC device of claim 11 , wherein the at least a subset of the one or more inter-kernel channels is sized based upon predication of a respective inter-kernel channel being sized.

16 . The IC device of claim 11 , wherein the at least a subset of the one or more inter-kernel channels is sized based upon scheduling imbalances of kernels connected to a respective inter-kernel channel being sized.

17 . The IC device of claim 11 , wherein the at least a subset of the one or more inter-kernel channels is sized based upon a latency of a respective inter-kernel channel being sized, predication of the respective inter-kernel channel being sized, and scheduling imbalances of kernels connected to the respective inter-kernel channel being sized.

18 . A method, comprising:
sizing, via a compiler, one or more inter-kernel channels based upon one or more program implementation factors, predication factors, kernel scheduling imbalance factors, or any combination thereof determined by the compiler; and providing sizing information regarding the sizing to an integrated circuit for implementation of the inter-kernel channel on the integrated circuit, according to the sizing.

19 . The method of claim 18 , wherein the sizing of the one or more inter-kernel channels is based upon a latency of a respective inter-kernel channel being sized, predication of the respective inter-kernel channel being sized, scheduling imbalances of kernels connected to the respective inter-kernel channel being sized, or any combination thereof.

20 . The method of claim 19 , comprising sizing at least one inter-kernel cha

Assignees

• Altera Corp

Inventors

• Baker Alan
• Ling Andrew Chaang
• Miriste Andrei Mihai Hagiescu

Classifications

• G06F30/327

  Logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist · CPC title

• G06F2115/08

  Intellectual property [IP] blocks or IP cores · CPC title

• G06F30/34 Primary

  for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD] · CPC title

• G06F9/544 Primary

  Buffers; Shared memory; Pipes · CPC title

• G06F9/54

  Interprogram communication · CPC title