Associative summing for high performance computing

Patent metadata

Field	Value
Publication number	US-2016239262-A1
Application number	US-201615041038-A
Country	US
Kind code	A1
Filing date	Feb 11, 2016
Priority date	Feb 12, 2015
Publication date	Aug 18, 2016
Grant date	—

Abstract

Apparatus, systems, and methods are described, including apparatus that includes one or more communication interfaces for communicating over a communication network, and a processor. The processor is configured to receive, via the communication interfaces, a plurality of numbers, and calculate a sum of the numbers that is independent of an order in which the numbers are received, by (i) converting any of the numbers that are received in a floating-point representation to a derived floating-point representation that includes a plurality of signed integer multiplicands corresponding to different respective orders of magnitude, and (ii) summing the numbers in the derived floating-point representation, by separately summing integer multiplicands that correspond to the same order of magnitude. Other embodiments are also described.

First claim

1 . Apparatus, comprising:
one or more communication interfaces for communicating over a communication network; and a processor, configured to:
receive, via the communication interfaces, a plurality of numbers, and
calculate a sum of the numbers that is independent of an order in which the numbers are received, by:
converting any of the numbers that are received in a floating-point representation to a derived floating-point representation that includes a plurality of signed integer multiplicands corresponding to different respective orders of magnitude, and
summing the numbers in the derived floating-point representation, by separately summing integer multiplicands that correspond to the same order of magnitude.

2 . The apparatus according to claim 1 , wherein the apparatus is a network switch,
the communication interfaces being ports belonging to the network switch, and the processor being a processor of the network switch.

3 . The apparatus according to claim 1 , wherein the apparatus is a network interface controller (NIC),
the communication interfaces being ports belonging to the NIC, and the processor being a processor of the NIC.

4 . The apparatus according to claim 1 , wherein the processor is further configured to:
convert the sum of the numbers from the derived floating-point representation to the floating-point representation, and subsequently, communicate the sum to one or more nodes on the network.

5 . The apparatus according to claim 1 , wherein the derived floating-point representation includes a sufficient number of bits such as to represent any given number that is received in the floating-point representation without any loss of precision relative to the floating-point representation.

6 . The apparatus according to claim 1 , wherein the communication network includes a High Performance Computing (HPC) network, and wherein the numbers are respective partial results of a parallel computing task performed on the HPC network.

7 . The apparatus according to claim 1 , wherein the derived floating-point representation further includes an integer indicator that indicates a highest order of magnitude of the orders of magnitude.

8 . The apparatus according to claim 7 , wherein the processor is configured to sum a first number and a second number in the derived floating-point representation by:
computing a non-negative difference D between (i) the integer indicator of the first number, and (ii) the integer indicator of the second number, aligning the second number with the first number, by shifting the integer multiplicands of the second number by D positions, and subsequently, separately summing each pair of integer multiplicands that are at the same position.

9 . The apparatus according to claim 1 , wherein each of the signed integer multiplicands includes a plurality of B magnitude bits, and wherein a number of integer multiplicands in the derived floating-point representation is a smallest integer N for which B*(N−1)>=M−1, M being a number of mantissa bits in the floating-point representation.

10 . The apparatus according to claim 9 , wherein each of the signed integer multiplicands further includes at least one overflow magnitude bit, and wherein the processor is configured to use the overflow magnitude bit to store any sum of integer multiplicands that is greater than 2 B −1.

11 . A system, comprising:
a plurality of networked computers; and at least one network switch, configured to:
receive, from the computers, a plurality of numbers, and
calculate a sum of the numbers that is independent of an order in which the numbers are received, by:
converting any of the numbers that are received in a floating-point representation to a derived floating-point representation that includes a plurality of signed integer multiplicands corresponding to different respective orders of magnitude, and
summing the numbers in the derived floating-point representation, by separately summing integer multiplicands that correspond to the same order of magnitude.

12 . The system according to claim 11 , wherein the network switch is further configured to:
convert the sum of the numbers from the derived floating-point representation to the floating-point representation, and subsequently, communicate the sum to the computers.

13 . The system according to claim 11 , wherein the derived floating-point representation includes a sufficient number of bits such as to represent any given number that is received in the floating-point representation without any loss of precision relative to the floating-point representation.

14 . The system according to claim 11 , wherein the numbers are respective partial results of a parallel computing task performed by the computers.

15 . The system according to claim 11 , wherein the derived floating-point representation further includes an integer indicator that indicates a highest order of magnitude of the orders of magnitude.

16 . The system according to claim 11 , wherein the network switch is configured to sum a first number and a second number in the derived floating-point representation by:
computing a non-negative difference D between (i) the integer indicator of the first number, and (ii) the integer indicator of the second number, aligning the second number with the first number, by shifting the integer multiplicands of the second number by D positions, and subsequently, separately summing each pair of integer multiplicands that are at the same position.

17 . The system according to claim 11 , wherein each of the signed integer multiplicands includes a plurality of B magnitude bits, and wherein a number of integer multiplicands in the derived floating-point representation is a smallest integer N for which B*(N−1)>=M−1, M being a number of mantissa bits in the floating-point representation.

18 . The system according to claim 17 , wherein each of the signed integer multiplicands further includes at least one overflow magnitude bit, and wherein the network switch is configured to use the overflow magnitude bit to store any sum of integer multiplicands that is greater than 2 B −1.

19 . A method, comprising, using a network switch:
receiving a plurality of numbers; and calculating a sum of the numbers that is independent of an order in which the numbers are received, by:
converting any of the numbers that are received in a floating-point representation to a derived floating-point representation that includes a plurality of signed integer multiplicands corresponding to different respective orders of magnitude, and
summing the numbers in the derived floating-point representation, by separately summing integer multiplicands that correspond to the same order of magnitude.

20 . A computer software product comprising a tangible non-transitory computer-readable medium in which program instructions are stored, which instructions, when read by a processor, cause the processor to:
receive a plurality of numbers, and calculate a sum of the numbers that is independent of an order in which the numbers are received, by:
converting any of the numbers that are received in a floating-point representation to a derived floating-point representation that includes a plurality of signed integer multiplicands corresponding to different respective orders of magnitude, and
summing the numbers in the derived floating-point representation, by separately summing integer multiplicands that correspond to the same order of magnitude.

Assignees

• Mellanox Technologies Ltd

Inventors

• Chapman Hillel

Classifications

• H04L67/10 Primary

  in which an application is distributed across nodes in the network (software deployment G06F8/60; multiprogramming arrangements G06F9/46) · CPC title

• G06F7/485

  Adding; Subtracting {(G06F7/4833, G06F7/4836 take precedence)} · CPC title

• G06F5/00 Primary

  Methods or arrangements for data conversion without changing the order or content of the data handled · CPC title