# US 2025/0068421 A1 · Implementing specialized instructions for accelerating dynamic programming algorithms

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2025/0068421 A1
- Document ID: US20250068421A1
- Status: Published application
- Kind: A1
- Application number: 18/908,678
- Filed: 2024-10-07
- Published: 2025-02-27
- Earliest claimed: 2021-09-30
- Assignees: NVIDIA Corporation
- Applicants: NVIDIA Corporation
- Inventors: Maciej Piotr TYRLIK; Ajay Sudarshan TIRUMALA; Shirish GADRE; Frank Joseph EATON; Daniel Alan STIFFLER
- Web page: https://patentgrep.com/patent/US20250068421A1

## CPC

- G06F 9/30014: {with variable precision}
- G06F 9/30065: {Loop control instructions; iterative instructions, e.g. LOOP, REPEAT}
- G06F 9/30021: {Compare instructions, e.g. Greater-Than, Equal-To, MINMAX}
- G06F 9/30038: {using a mask}
- G06F 9/30072: {to perform conditional operations, e.g. using predicates or guards}
- G06F 9/3851: {from multiple instruction streams, e.g. multistreaming}
- G06F 9/3887: {controlled by a single instruction for multiple data lanes [SIMD]}
- G06F 9/38875: {for adaptable or variable architectural vector length}
- G06F 9/3888: {controlled by a single instruction for multiple threads [SIMT] in parallel}
- G06F 9/38885: {Divergence aspects}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Various techniques for accelerating dynamic programming algorithms are provided. For example, a fused addition and comparison instruction, a three-operand comparison instruction, and a two-operand comparison instruction are used to accelerate a Needleman-Wunsch algorithm that determines an optimized global alignment of subsequences over two entire sequences. In another example, the fused addition and comparison instruction is used in an innermost loop of a Floyd-Warshall algorithm to reduce the number of instructions required to determine shortest paths between pairs of vertices in a graph. In another example, a two-way single instruction multiple data (SIMD) floating point variant of the three-operand comparison instruction is used to reduce the number of instructions required to determine the median of an array of floating point values.

## Claims

### Claim 1

A computer-implemented method for executing dynamic programming algorithms on parallel processors, the method comprising:
during a first iteration of a loop of a dynamic programming algorithm, executing at least one of a first fused addition and comparison instruction, a first three-operand comparison instruction, or a first two-operand comparison instruction that indicates a first source operand associated with a first destination operand to determine a first result; and
during a second iteration of the loop, executing at least one of a second fused addition and comparison instruction, a second three-operand comparison instruction, or a second two-operand comparison instruction that indicates a second source operand associated with a second destination operand to determine a second result based on the first result.
