公开(公告)号：US12141582B2

公开(公告)日：2024-11-12

申请号：US17936172

申请日：2022-09-28

Applicant: NVIDIA CORPORATION

Inventor： Maciej Piotr Tyrlik ,  Ajay Sudarshan Tirumala ,  Shirish Gadre ,  Frank Joseph Eaton ,  Daniel Alan Stiffler

IPC: G06F9/30 ,  G06F9/38

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.