Apparatus, methods, and systems for unstructured data flow in a configurable spatial accelerator with predicate propagation and merging

Patent metadata

Field	Value
Publication number	US-11307873-B2
Application number	US-201815944546-A
Country	US
Kind code	B2
Filing date	Apr 3, 2018
Priority date	Apr 3, 2018
Publication date	Apr 19, 2022
Grant date	Apr 19, 2022

Abstract

Systems, methods, and apparatuses relating to unstructured data flow in a configurable spatial accelerator are described. In one embodiment, a configurable spatial accelerator includes a data path having a first branch and a second branch, and the data path comprises at least one processing element; a switch circuit comprising a switch control input to receive a first switch control value to couple an input of the switch circuit to the first branch and a second switch control value to couple the input of the switch circuit to the second branch; a pick circuit comprising a pick control input to receive a first pick control value to couple an output of the pick circuit to the first branch and a second pick control value to couple the output of the pick circuit to a third branch of the data path; a predicate propagation processing element to output a first edge predicate value and a second edge predicate value based on (e.g., both of) a switch control value from the switch control input of the switch circuit and a first block predicate value; and a predicate merge processing element to output a pick control value to the pick control input of the pick circuit and a second block predicate value based on both of a third edge predicate value and one of the first edge predicate value or the second edge predicate value.

First claim

What is claimed is:

1. An apparatus comprising:
a data path having a first branch and a second branch, and the data path comprising at least one processing element;
a switch circuit comprising a switch control input to receive a first switch control value to couple an input of the switch circuit to the first branch and a second switch control value to couple the input of the switch circuit to the second branch;
a pick circuit comprising a pick control input to receive a first pick control value to couple an output of the pick circuit to the first branch and a second pick control value to couple the output of the pick circuit to a third branch of the data path;
a predicate propagation processing element to simultaneously output a first edge predicate value and a second edge predicate value based on both of a switch control value from the switch control input of the switch circuit and a first block predicate value; and
a predicate merge processing element to simultaneously output a pick control value to the pick control input of the pick circuit and a second block predicate value based on both of a third edge predicate value and one of the first edge predicate value or the second edge predicate value.

2. The apparatus of claim 1 , wherein a second predicate propagation processing element is coupled to the predicate propagation processing element to send the first block predicate value to the predicate propagation processing element based on at least a switch control value from a switch control input of a second switch circuit of the data path.

3. The apparatus of claim 2 , wherein the second predicate propagation processing element is coupled to the predicate merge processing element to send the third edge predicate value to the predicate merge processing element based on at least the switch control value from the switch control input of the second switch circuit of the data path.

4. The apparatus of claim 1 , wherein a second predicate merge processing element is coupled to the predicate merge processing element to send the third edge predicate value to the predicate merge processing element based on at least a pick control value from a pick control input of a second pick circuit of the data path.

5. The apparatus of claim 1 , wherein the predicate propagation processing element is to output:
a false value as the first edge predicate value and a false value as the second edge predicate value when the first block predicate value is a false value;
a true value as the first edge predicate value and a false value as the second edge predicate value when the first block predicate value is a true value and the switch control value from the switch control input of the switch circuit is a false value; and
a false value as the first edge predicate value and a true value as the second edge predicate value when the first block predicate value is a true value and the switch control value from the switch control input of the switch circuit is a true value.

6. The apparatus of claim 5 , wherein the predicate merge processing element is to output:
a false value as the second block predicate value and no value for the pick control value to the pick control input when the third edge predicate value is a false value and the one of the first edge predicate value or the second edge predicate value is a false value;
a true value as the second block predicate value and a false value as the pick control value to the pick control input when the third edge predicate value is a true value and the one of the first edge predicate value or the second edge predicate value is a false value; and
a true value as the second block predicate value and a true value as the pick control value to the pick control input when the third edge predicate value is a false value and the one of the first edge predicate value or the second edge predicate value is a true value.

7. The apparatus of claim 1 , wherein the predicate merge processing element is to output:
a false value as the second block predicate value and no value for the pick control value to the pick control input when the third edge predicate value is a false value and the one of the first edge predicate value or the second edge predicate value is a false value;
a true value as the second block predicate value and a false value as the pick control value to the pick control input when the third edge predicate value is a true value and the one of the first edge predicate value or the second edge predicate value is a false value; and
a true value as the second block predicate value and a true value as the pick control value to the pick control input when the third edge predicate value is a false value and the one of the first edge predicate value or the second edge predicate value is a true value.

8. The apparatus of claim 1 , wherein the predicate propagation processing element is to stall sending of the one of the first edge predicate value or the second edge predicate value to the predicate merge processing element when a backpressure signal from the predicate merge processing element indicates that storage in the predicate merge processing element is not available for the one of the first edge predicate value or the second edge predicate value.

9. A method comprising:
receiving, on a switch control input of a switch circuit, a first switch control value to couple an input of the switch circuit to a first branch of a data path or a second switch control value to couple the input of the switch circuit to a second branch of the data path, the data path comprising at least one processing element;
receiving, on a pick control input of a pick circuit, a first pick control value to couple an output of the pick circuit to the first branch and a second pick control value to couple the output of the pick circuit to a third branch of the data path;
simultaneously outputting, by a predicate propagation processing element, a first edge predicate value and a second edge predicate value based on both of a switch control value from the switch control input of the switch circuit and a first block predicate value; and
simultaneously outputting, by a predicate merge processing element, a pick control value to the pick control input of the pick circuit and a second block predicate value based on both of a third edge predicate value and one of the first edge predicate value or the second edge predicate value.

10. The method of claim 9 , further comprising a second predicate propagation processing element sending the first block predicate value to the predicate propagation processing element based on at least a switch control value from a switch control input of a second switch circuit of the data path.

11. The method of claim 10 , further comprising the second predicate propagation processing element sending the third edge predicate value to the predicate merge processing element based on at least the switch control value from the switch control input of the second switch circuit of the data path.

12. The method of claim 9 , further comprising a second predicate merge processing element sending the third edge predicate value to the predicate merge processing element based on at least a pick control value from a pick control input of a second pick circuit of the data path.

13. The method of claim 9 , further comprising the predicate propagation processing element outputting:
a false value as the first edge predicate value and a false value as the second edge predicate value when the first block predicate value is a false value;
a true value as the first edge predicate value and a false value as the second edge predicate value when the first block pre

Assignees

• Intel Corp

Inventors

• Halpern Pablo
• Fleming Kermin E
• Sukha James

Classifications

• G06F9/3005

  to perform operations for flow control · CPC title

• G06F9/323

  for indirect branch instructions · CPC title

• G06F15/825

  Dataflow computers · CPC title

• Y02D10/00

  Energy efficient computing, e.g. low power processors, power management or thermal management · CPC title

• G06F9/3836 Primary

  Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution · CPC title