Optimal deployment of embeddings tables across heterogeneous memory architecture for high-speed recommendations inference

A system for high speed recommendations, the system comprising:

• a memory storing instructions;
• one or more Input/Output (I/O) interfaces;
• and
• one or more hardware processors coupled to the memory via the one or more I/O interfaces, wherein the one or more hardware processors are configured by the instructions to:
• receive, by an optimizer executed by one or more hardware processors, a plurality of input parameters comprising (i) a memory configuration of a heterogeneous memory architecture used by a Recommendation Model (RM) during inference, the heterogenous memory architecture comprising a first level memory and a second level memory of a Field Programmable Gate Array (FPGA) accelerator, and a CPU memory type, (ii) an access latency of each memory type of the heterogeneous memory architecture, (iii) a total number of tables in the RM, (iv) a plurality of embedding tables, (v) a Cumulative Distributive Function (CDF) depicting probability distribution of queries satisfied by caching a plurality of records from the plurality of embedding tables, (vi) an input access pattern obtained from the CDF, and (vii) a table access pattern of each table from the total number of tables;
• obtain, by the optimizer executed by the one or more hardware processors:
• a) an estimated memory utilization for (i) a number of records cached in the first level memory and the second level memory, and (ii) a plurality of parameters of a learned indices technique stored in one of memory sub-types not used for caching embeddings in the first level memory used for addressing the plurality of records cached in the first level memory and the second level memory;
• and
• b) a latency model for each memory type using the CDF, the input access pattern, the table access pattern, the access latency of each memory type, a replication factor indicating number of times a record among the plurality of records is replicated in the first level memory and the second level memory for multiple parallel access an initial partition information (table partition, memory type) indicating number of records from each of the plurality of embedding tables being cached in each memory type, and a number of round trips to each memory unit of the second level memory;
• dynamically generate, by the optimizer executed by the one or more hardware processors, a final partition information and a final replication factor, from the latency model, the estimated memory utilization, and a plurality of constraints using an iterative process until latency described in the latency model is minimized, wherein the plurality of constraints,
• a) ensure estimated memory utilization,
• (i) for the first level memory is within an available memory capacity of first level memory received in the memory configuration,
• (ii) for the second level memory is such that top k largest table partitions among a plurality of sorted table partitions generated during the estimation of round trips to each memory unit of the second level memory is within the capacity of a largest memory sub-type with k memory units in the second level memory, and
• (iii) for the second level memory such that non-top k largest table partitions among the plurality of sorted table partitions are within the capacity of memories other than the largest memory sub-type in the second level memory,
• b) restrict the number of round trips to each memory unit of the first level memory used for caching embeddings to ‘one’ to avoid partition of multiple embedding tables on a single memory unit among a plurality of memory units within the first level memory used for caching embeddings,
• c) restrict estimated memory utilization by the learned indices technique is within the capacity of one of the memory sub-types not used for caching embeddings in the first level memory, and
• d) ensure non-cached records are pushed to the CPU memory;
• and
• dynamically map each table partition of the final partition information to one of the first level memory and the second level memory by a heterogenous mapper executed by the one or more hardware processors on receiving a shuffle signal triggered due to change in the input access pattern, wherein the mapping defines an approach to cache the plurality of records into the first level memory and the second level memory, and wherein the mapping comprises:
• a) each table partition of the final partition information to a memory unit of the first level memory using final replication factor of first level memory, an embedding record dimension of each of the plurality of embedding tables, a width, and a size of the memory unit of the first level memory received in the memory configuration, wherein the width refers to number of bits that can be stored in a single row of memory unit of the first level memory, and
• b) each table partition of the final partition information to a memory unit of the second level memory based on the final replication factor of the second level memory and round trips to each memory unit of the second level memory.

One or more non-transitory machine-readable information storage mediums comprising one or more instructions which when executed by one or more hardware processors cause:

• receiving a plurality of input parameters comprising (i) a memory configuration of a heterogeneous memory architecture used by a Recommendation Model (RM) during inference, the heterogenous memory architecture comprising a first level memory and a second level memory of a Field Programmable Gate Array (FPGA) accelerator, and a CPU memory type, (ii) an access latency of each memory type of the heterogeneous memory architecture, (iii) a total number of tables in the RM, (iv) a plurality of embedding tables, (v) a Cumulative Distributive Function (CDF) depicting probability distribution of queries satisfied by caching a plurality of records from the plurality of embedding tables, (vi) an input access pattern obtained from the CDF, and (vii) a table access pattern of each table from the total number of tables;
• obtaining by the optimizer:
• a) an estimated memory utilization for (i) a number of records cached in the first level memory and the second level memory, and (ii) a plurality of parameters of a learned indices technique stored in one of memory sub-types not used for caching embeddings in the first level memory used for addressing the plurality of records cached in the first level memory and the second level memory;
• and
• b) a latency model for each memory type using the CDF, the input access pattern, the table access pattern, the access latency of each memory type, a replication factor indicating number of times a record among the plurality of records is replicated in the first level memory and the second level memory for multiple parallel access, an initial partition information (table partition, memory type) indicating number of records from each of the plurality of embedding tables being cached in each memory type, and a number of round trips to each memory unit of the second level memory;
• dynamically generating a final partition information and a final replication factor, from the latency model, the estimated memory utilization, and a plurality of constraints using an iterative process until latency described in the latency model is minimized, wherein the plurality of constraints,
• a) ensure estimated memory utilization,
• (i) for the first level memory is within an available memory capacity of first level memory received in the memory configuration,
• (ii) for the second level memory is such that top k largest table partitions among a plurality of sorted table partitions generated during the estimation of round trips to each memory unit of the second level memory is within the capacity of a largest memory sub-type with k memory units in the second level memory, and
• (iii) for the second level memory such that non-top k largest table partitions among the plurality of sorted table partitions are within the capacity of memories other than the largest memory sub-type in the second level memory,
• b) restrict the number of round trips to each memory unit of the first level memory used for caching embeddings to ‘one’ to avoid partition of multiple embedding tables on a single memory unit among a plurality of memory units within the first level memory used for caching embeddings,
• c) restrict estimated memory utilization by the learned indices technique is within the capacity of one of the memory sub-types not used for caching embeddings in the first level memory, and
• d) ensure non-cached records are pushed to the CPU memory;
• and
• dynamically mapping each table partition of the final partition information to one of the first level memory and the second level memory by a heterogenous mapper executed by the one or more hardware processors on receiving a shuffle signal triggered due to change in the input access pattern, wherein the mapping defines an approach to cache the plurality of records into the first level memory and the second level memory, and wherein the mapping comprises:
• a) each table partition of the final partition information to a memory unit of the first level memory using final replication factor of first level memory, an embedding record dimension of each of the plurality of embedding tables, a width, and a size of the memory unit of the first level memory received in the memory configuration, wherein the width refers to number of bits that can be stored in a single row of memory unit of the first level memory, and
• b) each table partition of the final partition information to a memory unit of the second level memory based on the final replication factor of the second level memory and round trips to each memory unit of the second level memory.