US20120324143A1

US20120324143A1 - Methods and apparatus for data access by a reprogrammable circuit module

Info

Publication number: US20120324143A1
Application number: US13/161,141
Authority: US
Inventors: John J. Giganti; Andrew Huo; Richard A. Baum; John M. Cavallo
Original assignee: Data Design Corp
Current assignee: Data Design Corp
Priority date: 2011-06-15
Filing date: 2011-06-15
Publication date: 2012-12-20
Also published as: GB2491979A; US8838873B2; WO2012174043A1; TW201314453A; US20120324149A1; EP2535820A3; GB2491979B; GB201210639D0; EP2535820A2

Abstract

In some embodiments, an apparatus includes a set of memory modules, a reprogrammable circuit module and a set of data channels. Each memory module is associated with an address translation table configured to store a set of address pairs each including a physical memory address and a logical memory address. The reprogrammable circuit module is configured to retrieve a first physical memory address associated with a first logical memory address and a second physical memory address associated with a second logical memory address. Each data channel couples the reprogrammable circuit module to at least one memory module. The reprogrammable circuit module is configured to send a first and a second query to the first and the second memory module, via a first data channel based on the first physical memory address or a second data channel based on the second physical memory address, respectively.

Description

BACKGROUND

Some embodiments described herein relate generally to memory systems, and, in particular, to systems and methods for accessing data from a memory system using a reprogrammable circuit module.
Some known systems for performing database searches employ an array of individual computers each programmed to perform a similar search function on one or more databases, in order to increase the speed of retrieving data from the databases. Such a scheme, however, is difficult to manage and coordinate different computers. Some other known systems use an array of disk drives connected to an array of processor units. To perform a search function, data is read from the disk drives and processed at the processor units. With this approach, large amount of data is transmitted from the disk drives to the processors, which causes a substantial latency in retrieving data.
Accordingly, a need exists for a system where high speed database searches can be performed, and particularly, improvement in speed over the existing design using disk drives can be achieved.

SUMMARY

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a system block diagram of a reprogrammable circuit module coupled to a set of memory modules, according to an embodiment.

FIG. 2 is a schematic illustration of structure of a memory module, according to an embodiment.

FIG. 3 is a schematic illustration of an address translation table stored in a memory module, according to an embodiment.

FIG. 4 is a schematic illustration of a reprogrammable circuit module configured to execute a search process, according to an embodiment.

FIG. 5 is a flow chart illustrating a method for executing a search process on multiple memory modules, according to an embodiment.

DETAILED DESCRIPTION

In some embodiments, an apparatus includes a set of memory modules, a reprogrammable circuit module and a set of data channels. Each memory module from the set of memory modules is associated with an address translation table configured to store a set of address pairs, where each address pair includes (1) a physical memory address associated with a physical location in a memory module from the set of memory modules and (2) a logical memory address associated with the physical memory address. The reprogrammable circuit module is configured to execute a search process based at least in part on data stored at the set of memory modules. The search process is configured to retrieve a first physical memory address associated with a first logical memory address from an address translation table associated with a first memory module from the set of memory modules, and a second physical memory address associated with a second logical memory address from an address translation table associated with a second memory module from the set of memory modules. In some embodiments, the reprogrammable circuit module is configured to randomly associate the first physical memory address with the first logical memory address and randomly associate the second physical memory address with the second logical memory address, such that the first logical memory address is adjacent to the second logical memory address while the first physical memory address is not adjacent to the second physical memory address.
Furthermore, each data channel from the set of data channels operably couples the reprogrammable circuit module to at least one memory module from the set of memory modules. The reprogrammable circuit module is configured to send, based on the search process, a first query to the first memory module via a first data channel from the set of data channels based on the first physical memory address and a second query to the second memory module via a second data channel from the set of data channels based on the second memory address. In some embodiments, the reprogrammable circuit module is configured to send the first query at substantially a same time as the second query. In some embodiments, the reprogrammable circuit module is a Field Programmable Gate Array (FPGA), and configured to be modified by a driver module. In some embodiments, each memory module from the set of memory modules is a flash memory module included in a dual in-line memory module (DIMM), and the set of memory modules are removably coupled to a Peripheral Component Interconnect Express (PCIe) card including the reprogrammable circuit module.
In some embodiments, an apparatus comprises a first reprogrammable circuit module and a memory package including a set of memory modules. The memory package is removably coupled to the first reprogrammable circuit module. Specifically, the memory package is operatively coupled to the first reprogrammable circuit module via a set of channels when in a first configuration, and physically coupled to a second reprogrammable circuit module when in a second configuration. At least one memory module from the set of memory modules is configured to store an address translation table having a set of address pairs associated with the set of memory modules. Each address pair from the set of address pairs includes (1) a physical memory address associated with a physical location in the set of memory modules and (2) a logical memory address associated with the physical memory address. In some embodiments, the memory package is a DIMM, where each memory module from the set of memory modules is a flash memory module on the DIMM. In some embodiments, the first reprogrammable circuit module is a FPGA.
Furthermore, the first reprogrammable circuit module is configured to use the set of address pairs to execute a search process via the set of channels after the memory package is moved from the second configuration to the first configuration, where the search process is substantially the same as a search process executed by the second reprogrammable circuit module when the memory package is in the second configuration. The search process executed by the first reprogrammable circuit module is configured to retrieve a physical memory address associated with a received logical memory address using the address translation table. Furthermore, in some embodiments, the first reprogrammable circuit module is configured to send a first query to a first memory module from the set of memory modules during a first time period, and send a second query to a second memory module from the set of memory modules during a second time period overlapping the first time period.
FIG. 1 is a system block diagram of a reprogrammable circuit module 120 coupled to a set of memory modules (e.g., memory modules 161-166), according to an embodiment. The reprogrammable circuit module 120 is a portion of an expansion board 100, which is operatively coupled to a host computer 110. The set of memory modules, including memory modules 161-166, are included in a replaceable memory package 140 that is coupled to the expansion board 100 via a socket 150. Furthermore, each memory module from the set of memory modules in the memory package 140 is operatively coupled to reprogrammable circuit module 120 via a data channel, such as data channels 131, 132 and 133 shown in FIG. 1.
As shown in FIG. 1 and further described below, the expansion board 100 contains an implementation of a scalable structure that is synthesized by connecting multiple parallel channels (e.g., data channels 131-133) of high data rate memory modules (e.g., memory modules 161-166) directly to a data-processing module (e.g., reprogrammable circuit module 120). In other words, an array of memory modules is connected to a single large data-processing module, where each memory module has its own data channel, thus to provide a combined transfer rate of up to a multiple times of the data rate for a single data channel. In some embodiments, such an integrated structure consisting of a single data-processing module connected to an array of memory modules (typically flash memory devices) is referred to as a Flash Processing Element (FPE). In some embodiments, a scalable implementation of a FPE is known as a Scalable Large Flash Memory (SLFM) system.
The expansion board 100 can be any removable device that can be used to implement a FPE structure, i.e., to access and retrieve data stored in the memory package 140, and locally process the retrieved data within the expansion board 100. Specifically, reprogrammable circuit module 120 can be used to access and retrieve data from the memory modules (e.g., memory modules 161-166) included in the memory package 140 via the data channels (e.g., data channels 131-133), and then process the retrieved data within the expansion board 100. For example, the expansion board 100 can be an add-in circuit board directly coupled to a motherboard of a PC. For another example, the expansion board 100 can be a removable module connected to a processor of a computer server via an interface and/or a bus. Furthermore, the expansion board 100 can be operatively coupled to host computer 110 via for example, a high speed serial data and/or command interface over a data channel. In some embodiments, the expansion board 100 can be connected to a motherboard of host computer 110.
In some embodiments, the expansion board 100 can be a PCIe card. In such embodiments, the FPE system including reprogrammable circuit module 120, the memory package 140 and other components (not shown in FIG. 1) are contained on the PCIe expansion board 100. Physical implementation of the I/O channel connecting the expansion board 100 and host computer 120 can be in a PCIe format, and the expansion board 100 can be accessible with a unique PCIe address. The PCIe format allows multiple FPE boards, including the expansion board 100, to be used in a variety of configurations from single board applications to systems needing hundreds of FPEs. These FPE boards (i.e., PCIe cards such as the expansion board 100) are physically compatible with common full length PCI slots of a PC or a PCIe expansion chassis. Furthermore, such a PCIe card can be connected to a motherboard or a host computer via a high speed serial data or command interface over a multi-lane PCIe channel, which can provide a large data rate (e.g. 5 G bytes/sec). Additionally, in some embodiments, the expansion board 100 can be a circuit board that adopts the Advanced Telecommunications Computing Architecture (ATCA) backplane interface specification or any other interface specification.
Reprogrammable circuit module 120 can be any circuit module that is capable of retrieving data from the memory package 140. In some embodiments, reprogrammable circuit module 120 can be capable of on-board processing of retrieved data. In some embodiments, reprogrammable circuit module 120 can be a FPGA. For example, reprogrammable circuit module 120 can be an Altera Stratix 4GX-530 FPGA. More specifically, reprogrammable circuit module 120 can be a FPGA consisting of a large number of logic elements and/or data-processing elements, which is programmed to retrieve data stored at memory modules in the memory package 140 and further process the retrieved data within reprogrammable circuit module 120. In other embodiments, a reprogrammable circuit module can be an application-specific integrated circuit (ASIC) or any other suitable programmable logic device (PLD), such as a programmable logic array (PLA), a programmable array logic (PAL), a complex programmable logic device (CPLD), etc.
Particularly, reprogrammable circuit module 120 can be used to perform a search function. That is, reprogrammable circuit module 120 can be configured to search specific data (e.g., a string, a term) from the data stored within the memory modules included in the memory package 140. Details of a reprogrammable circuit module being configured to perform a search function are described with respect to FIGS. 4-5.
In some embodiments, reprogrammable circuit module 120 includes an on-board configuration storage, such as an on-board configuration ROM (read-only memory), to store a configuration file. The configuration ROM, although not shown in FIG. 1, can be mounted on the expansion board 100 and electrically coupled to reprogrammable circuit module 120. The configuration file contained in the configuration ROM can be automatically uploaded from the configuration ROM into reprogrammable circuit module 120 upon the application of power at the beginning of a system boot-up. As a result, reprogrammable circuit module 120 is configured to operate according to the uploaded configuration file, such as to perform a specific task (e.g., a search function). Furthermore, a new configuration file can be loaded into the on-board configuration ROM of the expansion board 100 at any time after a system boot-up, and further uploaded into reprogrammable circuit module 120 (e.g., at next system boot-up), such that reprogrammable circuit module 120 can be “reprogrammed” to perform a different task if necessary.
In some embodiments, reprogrammable circuit module 120 can also be configured, or “reprogrammed”, by a driver module (not shown in FIG. 1), which is typically located at host computer 110. As a tool to configure reprogrammable circuit module 120 from the host computer 110, the driver module can optimize a program (e.g., a FPGA program) for a given task that is to be executed by reprogrammable circuit module 120, and then send the program to reprogrammable circuit module 120. For example, as different search programs use different criteria, a user can write a VHDL (VHSIC hardware description language) program for a given search algorithm, and then send the VHDL program to reprogrammable circuit module 120 from the host computer 110 using the driver module. As a result, reprogrammable circuit module 120 will adjust accordingly and execute the search function according to the VHDL program. In other embodiments, other programming languages such as Verilog or other HDL languages can be used to reprogram or configure reprogrammable circuit module 120.
As shown in FIG. 1, the memory package 140 contains multiple memory modules, such as memory modules 161-166. A memory module in the memory package 140 can be any type of memory device that can be used to store data and can be accessed by reprogrammable circuit module 120 via, for example, a data channel (e.g., data channel 131-133). In some embodiments, a memory module can be a flash memory device, such as a multi-level cell (MLC) Not AND (NAND) chip, a single level cell (SLC) NAND chip, or a Clear NAND chip, etc. To support a particular type of memory device, reprogrammable circuit module 120 can be adjusted accordingly. For example, a FPGA internal state machine providing readout of the memory devices can be changed according to the specific type of memory devices. In some embodiments, the memory modules in a single memory package (e.g., memory package 140) can be instances of a same type of memory devices.
In some embodiments, each memory module contained in the memory package 140 is associated with an address translation table, which is from a set of one or more address translation tables stored in one or more memory modules contained in the memory package 140. That is, at least one memory segment unit in each memory module is associated with an entry of an address translation table stored in a memory module. For example, as shown in FIG. 1, each memory module contained in the memory package 140 is associated with address translation table 180, which is stored in memory module 162. Address translation table 180 can be configured to store a set of address pairs. Each address pair can include a physical memory address associated with a physical location in a memory module contained in the memory package 140, and a logical memory address associated with that physical memory address. Details of the internal structure of a memory module and an address translation table are further described with respect to FIGS. 2-3.
In some embodiments, although not shown in FIG. 1, more than one address translation table can be stored in the memory modules in the memory package 140. In such embodiments, for example, each memory module contained in the memory package 140 can be associated with a single address translation tables. For example, each memory module (e.g., memory module 161-166) contained in the memory package 140 can have its own address translation table, which is stored in the associated memory module. In that case, address translation table 180 is uniquely associated with memory module 162. Similarly stated, address translation table 180 is configured to store mapping information for memory segment units of memory module 162 but not the other memory modules including memory modules 161, 163-166, etc.
The memory package 140 can be any replaceable module that can contain one or more memory modules (e.g., memory modules 161-166) and enable the memory modules to be accessed by an on-board data-processing module (e.g., reprogrammable circuit module 120) via for example, one or more data channels (e.g., data channels 131-133). The memory package 140 is replaceable in the sense that it can be mounted onto any suitable circuit board via a suitable interface socket, or removed from the circuit board if necessary. For example, the memory package 140 can be mounted onto the expansion board 100 via a socket 150 when in a first configuration as shown in FIG. 1, or mounted onto another circuit board via another suitable interface socket (not shown in FIG. 1) when in a second configuration. As a result, the memory package can be physically coupled to reprogrammable circuit module 120 via a set of data channels (e.g., data channels 131-133) when in the first configuration, and physically coupled to another reprogrammable circuit module via a different set of data channels when in the second configuration.
Accordingly, the memory modules (e.g., memory modules 161-166) can be removed from the expansion board 100 containing the on-board data-processing module (e.g., reprogrammable circuit module 120) and other associated interface components (not shown in FIG. 1). The expansion board 100 can be used as a “carrier” board for one or more memory packages that include the memory modules. As a result, memory modules accessed by reprogrammable circuit module 120 can be easily replaced with for example, new types of memory modules, or same type of memory modules containing different data. Specifically, a memory package containing the old types of memory modules can be removed from an expansion board, and then a different memory package containing the new types of memory modules can be mounted onto the expansion board. Thus, this feature permits upgrading the memory modules to newer types as they become available, which greatly enhances the technology lifetime of the system. On the other hand, as described in detail with respect to FIGS. 4-5, reprogrammable circuit module 120 can be configured to execute a task such as a search function on the memory package 140 when the memory package 140 is coupled to reprogrammable circuit module 120 in the first configuration, where the search function is substantially the same as a search function executed by a different reprogrammable circuit module when the memory package is coupled to the different reprogrammable circuit module in the second configuration.
In some embodiments, the memory package 140 can be a DIMM. In such embodiments, the SLFM design using a DIMM as a memory package can be compatible with a variety of flash memory devices as memory modules, including MLC NAND chips, SLC NAND chips, Clear NAND chips, etc. Also, a DIMM flash mounting scheme uses DIMM slot connectors to mount the flash memory devices (e.g., memory modules 161-166) onto the memory package 140, which is then coupled to the expansion board via socket 150. For example, the memory package 140 can be a DIMM with a memory of 1T bytes that contains 16 Clear NAND chips, each of which has a memory of 64G bytes. Additionally, the use of the DIMM flash mounting scheme also permits alternative types of flash memory devices to be used on the memory package 140 without re-spinning the expansion board 100, by only providing a new DIMM containing the new type of flash memory devices, and adjusting reprogrammable circuit module 120 accordingly (e.g., changing the FPGA code consistent with the state machine requirements of the new part in reprogrammable circuit module 120).
As shown in FIG. 1, a set of data channels (e.g., data channels 131-133) operatively couple reprogrammable circuit module 120 to the memory modules (e.g., memory modules 161-166) contained in the memory package 140. A data channel can be used to convey any command, query or the like from reprogrammable circuit module 120 to a memory module, and/or send any retrieved data from the corresponding memory module to reprogrammable circuit module 120. Furthermore, the data channels are parallel to each other, in the sense that multiple data channels can be used at the same time to transmit data. For example, if there are 34 data channels connecting memory modules and reprogrammable circuit module 120, each having a speed of 200M byte/sec (e.g., using a double data rate (DDR) sync protocol), then an aggregate rate up to 6 G byte/sec can be provided.
In some embodiments, more than one memory module can be connected to reprogrammable circuit module 120 by a single data channel. For example, as shown in FIG. 1, memory modules 161, 162 are connected to reprogrammable circuit module 120 via data channel 131; memory modules 163, 164 are connected to reprogrammable circuit module 120 via data channel 132; memory modules 165, 166 are connected to reprogrammable circuit module 120 via data channel 133. Specifically, more than one memory module per data channel is made possible by exploiting the latency time of accessing a unit (e.g., a page) of data from a memory module, to interleave data accesses to multiple memory modules on the same data channel. For example, in the case of Clear NAND chips, the latency time is 150 usec. Since the page readout time is about 50 usec, it is possible to combine two chips on a single memory bus (i.e., data channel) with no loss of latency. Thus, the latency time between the receipt of a command selecting a page to be transferred and the beginning of transmission, is exploited to permit having multiple flash memory devices sharing a single data channel.
Furthermore, the number of memory modules (e.g., flash memory devices) that can be supported by reprogrammable circuit module 120 (e.g., a FPGA) can be limited by the I/O pin count of reprogrammable circuit module 120, as well as the internal logic resources of reprogrammable circuit module 120 needed to support the memory modules. The internal resources include for example, logic support for generating the state machine timing signals needed to meet the flash interface requirements, data buffers needed for alignment and error correction of the transferred pages, etc. For example, a Stratix EP4S530 FPGA has 744 I/O pins, allowing for various I/O interface standards needed by the FPGA to connect flashing memory devices and other components. As a result, a Stratix EP4S530 FPGA can support as many as 33 flash memory chips (e.g., contained in one or more memory packages).
FIG. 2 is a schematic illustration of structure of a memory module 200, according to an embodiment. Memory module 200 can be structurally and functionally similar to the memory modules 161-166 shown and described in FIG. 1. As shown in FIG. 2, memory module 200 stores an address translation table 210 and other data (e.g., data 251-254). Specifically, data is stored in a number of memory segment units. For example, data 251-254 is stored in four separate memory segment units, respectively. In some embodiments, a memory segment unit can be for example, a page. In some embodiments, an address translation table can be stored in one memory segment unit (as address translation table 210 shown in FIG. 2) or across multiple memory segment units.
Each memory segment unit in memory module 200 can be identified by, for example, a physical memory address representing a physical location of the starting point of that memory segment unit. A physical memory address can be for example, a binary number from a finite monotonically ordered sequence of binary numbers that uniquely describes the physical location of a memory itself. For example, as shown in FIG. 2, the memory segment unit where address translation table 210 is stored can be identified by a physical memory address 0x000000, which represents a physical location of the starting point of that memory segment unit. In this case it is also the starting point of the memory space of memory module 200. For another example, the memory segment unit where data 251 is stored can be identified by a physical memory address 0x000100, which represents a physical location of the starting point of that memory segment unit. Furthermore, as shown in FIG. 2, the physical memory addresses of the memory segment units form a monotonically-ordered (e.g., increasing, decreasing) sequence.
In some embodiments, a memory segment unit of memory module 200 can be accessed by for example, a reprogrammable circuit module (e.g., reprogrammable circuit module 120 in FIG. 1), based on the physical memory address identifying the memory segment unit. In some embodiments, a reprogrammable circuit module can be configured to search or retrieve the data stored in a memory segment unit of memory module 200 using the physical memory address identifying that memory segment unit to locate a starting point for the search or retrieving operation. For example, a reprogrammable circuit module can be configured to retrieve data 252 using physical memory address 0x000106 to locate a starting point for the retrieving operation. Particularly, a reprogrammable circuit module can be configured to search address translation table 210 using 0x000000 to locate a starting point for the search.
FIG. 3 is a schematic illustration of an address translation table 300 stored in a memory module, according to an embodiment. Address translation table 300 can be structurally and functionally similar to address translation table 180 or address translation table 210 shown in FIGS. 1-2, and accordingly, the memory module hosting address translation table 300 can be structurally and functionally similar to memory module 162 or memory module 200 shown in FIGS. 1-2. In some embodiments, an address translation table can be referred to as a block-address translation (BAT) table.
As shown in FIG. 3, address translation table 300 has two columns of entries, shown as logical memory address 310 and physical memory address 320. The first column, logical memory address 310, contains logical memory addresses (e.g., 1000, 1001, 1002, 1100), each of which uniquely identifies a logical memory address associated with a memory segment unit in a memory package including the memory module that hosts address translation table 300. A logical memory address can be in any suitable form and can represent a location, at which a memory segment unit (or other item such as a memory cell, a storage element, etc.) appears to reside from the perspective of a reprogrammable circuit module that performs a search function on the memory modules. In the example of FIG. 3, a logical memory address can be a four-digital integer, such as 1000, 1001, etc. In other embodiments a logical memory address can be in any other suitable form.
The second column, physical memory address 320, contains physical memory addresses (e.g., 465/0x002010, 463/0x006a24, 466/0x00f92a, 461/0x00ff00), each of which uniquely identifies a physical memory location of a memory segment unit in the memory package. In some embodiments, an address translation table stored in a memory module can store physical memory addresses identifying physical memory locations within other memory modules. In such embodiments, a physical memory address stored in this address translation table can include both information associated with a hosting memory module and information identifying a physical memory location within that hosting memory module. In the example of the physical memory address “465/002010” shown in FIG. 3, “465” identifies a memory module (i.e., memory module 465 shown in FIGS. 1) and “002010” identifies a memory segment unit, which is represented by a physical memory address “0x002010”, in the identified memory module 465. Overall, the physical memory address “465/002010” identifies the memory segment unit “0x002010” in memory module 465. Similarly, the physical memory address “463/006a24” identifies the memory segment unit “0x006a24” in memory module 463.
Address translation table 300 associates each logical memory address with a physical memory address. Specifically, each logical memory address stored in the column of logical memory address 310 can be mapped to a physical memory address stored in the column of physical memory address 320. For example, logical memory address “1000” is mapped to physical memory address “465/0x002010” in the first entry of address translation table 300. For another example, logical memory address “1001” is mapped to physical memory address “463/0x006a24” in the second entry of address translation table 300.
110381 In some embodiments, the logical memory addresses can be stored in a logical order in address translation table 300, such as a monotonically-increasing order as shown in FIG. 3. In such embodiments, the physical memory addresses are not necessarily stored in any logical order in address translation table 300. For example, the logical memory address stored in the first entry of address translation table 300 (i.e., 1000) is adjacent to the logical memory address stored in the second entry of address translation table 300 (i.e., 1001), while the physical memory address stored in the first entry (i.e., 465/0x002010), is not adjacent to the physical memory address stored in the second entry (i.e., 463/0x006a24). In fact, the two physical memory addresses identify two memory segment units in two different memory modules. In other embodiments, physical memory addresses can be stored in a logical order in address translation table 300.
In some embodiments, a reprogrammable circuit module can be configured to associate a physical memory address with a logical memory address stored in an address translation table. That is, the reprogrammable circuit module can be configured to assign a physical memory address to each logical memory address, and then store the pair of addresses (i.e., the physical memory address and the logical memory address) as an entry in the address translation table. Furthermore, in some embodiments, the reprogrammable circuit module can be configured to randomly assign a physical memory address to a logical memory address, such that the logical memory addresses are stored in a logical order in the address translation table, while the physical memory addresses associated with those logical memory addresses are randomly distributed across the entire available memory space provided by the memory modules, as shown in FIG. 3.
In some embodiments, a SLFM system described with respect to FIG. 1 can be used to execute a search function. FIG. 4 is a schematic illustration of such a SLFM system, including a reprogrammable circuit module 420 that is configured to execute a search process on a memory package 440, according to an embodiment. The structure of the system in FIG. 4 is similar to that of the system shown in FIG. 1. Specifically, reprogrammable circuit module 420 is a portion of an expansion board 400, which is operatively coupled to a host computer 410. A set of memory modules, including memory modules 461-466, are included in a replaceable memory package 440 that is coupled to the expansion board 400 via a socket 450. Each memory module from the set of memory modules in the memory package 440 is operatively coupled to reprogrammable circuit module 420 via a data channel, such as data channel 431-433.
A search process can be executed by the system shown in FIG. 4 as follows. Initially, a query is formulated in host computer 410 by for example, an operator or a user of host computer 410 and/or a program or application executing on host computer 410. An application running on host computer 410 can then be configured to translate the query into a set of machine executable tasks. In some embodiments, such a machine executable task can be for example, a string or a term of a predefined format (e.g., a fixed length) that can be searched against data stored in the memory modules on the memory package 440. Thus, the query is translated into a set of searchable strings or terms at host computer 410.
In some embodiments, one or more logical memory addresses associated with a searchable string or term can be determined based on the string or term. Specifically, a logical memory address is associated with a string or term in a sense that data stored in the memory segment unit represented by the logical memory address is likely to contain information associated with the string or term. Thus, to search for the string or term, data stored in the memory segment unit represented by the logical memory address needs to be searched. In some embodiments, the desired logical memory addresses can be determined at host computer 410, and then sent from host computer 410 to reprogrammable circuit module 420. In such embodiments, reprogrammable circuit module 420 is configured to receive the logical memory addresses. In some other embodiments, the desired logical memory addresses can be determined at reprogrammable circuit module 420 or another component of the system (not shown in FIG. 4). In such embodiments, the searchable string or term is sent from host computer 410 to reprogrammable circuit module 420 or the other component, where one or more logical memory addresses associated with the string or term are determined based on the string or term. The logical memory addresses are then sent to reprogrammable circuit module 420 if necessary. As a result, one or more logical memory addresses associated with the searchable string or term are available at reprogrammable circuit module 420. In the example of FIG. 4, reprogrammable circuit module 420 is configured to receive logical memory address 1001 and 1002 (e.g., as shown in FIG. 3) from host computer 410.
Next, reprogrammable circuit module 420 can be configured to send an address-translation query including the desired logical memory addresses to an address translation table stored in a memory module in the memory package 440 via a data channel. As shown in FIG. 4, reprogrammable circuit module 420 is configured to send an address-translation query, via data channel 431 (shown as data path 491), to memory module 462 contained in the memory package 440, where an address translation table 480 is stored. Similar to address translation table 180 shown in FIG. 1, address translation table 480 is associated with the memory modules contained in the memory package 440. That is, at least one memory segment unit in each memory module contained in the memory package 440 is associated with an entry stored in address translation table 480. In the example of FIG. 4, the address-translation query sent from reprogrammable circuit module 420 to memory module 462 includes the desired logical memory addresses 1001 and 1002.
In some embodiments, reprogrammable circuit module 420 can be configured to send more than one address-translation queries, each of which contains a different set of logical memory addresses and is destined to a different address translation table. For example, although not shown in FIG. 4, if entries associated with logical memory address 1001 and 1002 are stored in two different address translation tables in the memory package 440, then reprogrammable circuit module 420 can be configured to send a first address-translation query containing logical memory address 1001 to a first address translation table that includes an entry for logical memory address 1001, and send a second address-translation query containing logical memory address 1002 to a second address translation table that includes an entry for logical memory address 1002. Thus, every logical memory address is carried by an address-translation query that is sent to an appropriate address translation table containing an entry for the logical memory address.
After an address-translation query containing a logical memory address is received at an address translation table, an entry associated with the logical memory address can be determined based on the logical memory address. Physical memory address associated with the logical memory address can be retrieved from the entry, and sent to reprogrammable circuit module 420 via a data channel. In the example of FIG. 4, if address translation table 480 includes the same entries of address translation table 300 as shown in FIG. 3, then physical memory address “463/0x006a24” is associated with logical memory address 1001 and physical memory address. “466/0x00f92a” is associated with logical memory address 1002. That is, logical memory address 1001 points to a memory segment unit in memory module 463, which is identified by a physical memory address of “0x006a24” in memory module 463; and logical memory address 1002 points to a memory segment unit in memory module 466, which is identified by a physical memory address of “0x00f92a” in memory module 466. As a result of memory module 462 receiving the address-translation query containing logical memory addresses 1001 and 1002, physical memory addresses “463/0x006a24’ and “466/0x00f92a” are retrieved from address translation table 480 and sent to reprogrammable circuit module 420 via data channel 431 (shown as data path 492 in FIG. 4). Thus, a desired logical memory address available at reprogrammable circuit module 420 is used to retrieve a physical memory address, which can be used to locate a specific memory segment unit in a memory module within the memory package 440.
Subsequently, reprogrammable circuit module 420 can be configured to send one or more data queries to one or more memory segment units, each of which is identified by a retrieved physical memory address associated with a logical memory address. Specifically, a data query destined to a memory segment unit in a memory module within the memory package 440 can be sent over a data channel connecting reprogrammable circuit module 420 and the memory module. Furthermore, in some embodiments, multiple data queries to different memory modules can be sent from reprogrammable circuit module 420 at substantially a same time. In other words, a first data query can be sent to a first memory module during a first time period, and a second data query can be sent to a second memory module during a second time period overlapping the first time period. Thus, sending multiple data queries or retrieving data from multiple memory modules can be performed in a substantially simultaneous fashion via multiple data channels.
In the example of FIG. 4, after logical memory address 1001 and 1002 are translated into physical memory address “463/0x006a24” and “466/0x00f92a”, reprogrammable circuit module 420 is configured to send a first data query to a memory segment unit identified by physical memory address “0x006a24” in memory module 463 via data channel 432 (shown as data path 493), and a second data query to a memory segment unit identified by physical memory address “0x00f92a” in memory module 466 via data channel 433 (shown as data path 494). The first data query and the second data query can be sent at substantially a same time, and subsequently, data can be retrieved from memory module 463 and memory module 466 during a substantially same time period (shown as data path 495 and 496, respectively).
A data query sent from reprogrammable circuit module 420 to a memory segment unit in a memory module is designed to retrieve data from the memory segment unit. In some embodiments, data stored in the memory segment unit can be retrieved completely and the original data can be sent to reprogrammable circuit module 420 for further processing. In some other embodiments, data stored in the memory segment unit can be partially retrieved and sent to reprogrammable circuit module 420 for further processing, according to the data query. Further processing can include for example, search the desired string or term in the original data or processed data. Such further processing can be performed at reprogrammable circuit module 420, or alternatively, at another component of host computer 410.
In some embodiments, information of the associations between logical memory addresses and physical memory addresses with respect to memory segment units contained in a memory package can be stored in one or more address translation tables included in the memory package. In other words, the remapping information (e.g., between logical memory addresses and physical memory addresses) for a memory package can be carried by the one or more address translation tables included in the memory package. As a result, the memory package can be swapped from one circuit board to another that is suitable for the memory package, without loosing the remapping information. In the example of FIG. 4, address translation table 480 is configured to store the remapping information for the memory package 440. Therefore, the memory package 440 can be removed from the expansion board 400 and coupled to a different circuit board, where a task (e.g., a search function) can be executed in a substantially same way by a different reprogrammable circuit module as when the memory package 440 is coupled to the expansion board 400.
FIG. 5 is a flow chart illustrating a method for executing a search process on multiple memory modules, according to an embodiment. At 502, a query associated with a data lookup is received at a reprogrammable circuit module, where the query includes a first logical memory address and a second logical memory address. The data lookup can be part of a search process executed by the reprogrammable circuit module on a set of memory modules contained in a memory package. Specifically, the data lookup can be translated by for example, an application running on a host computer operatively coupled to the reprogrammable circuit module, into a set of queries including the received query. Each query contains one or more logical memory addresses used to retrieve a physical memory address, and/or some other associated information for the search process. The query including the first logical memory address and the second logical memory address is then sent from the host computer to the reprogrammable circuit module.
In the example shown and described with respect to FIG. 1, after a search process is initiated at host computer 110, a data lookup is generated at host computer 110. Subsequently, a query associated with the data lookup is generated by an application at host computer 110, and then sent to reprogrammable circuit module 120. The query includes a first logical memory address L1 and a second logical memory address L2. Furthermore, in some embodiments, the first logical memory address L1 and the second logical memory address L2 can be adjacent to each other in a logically-ordered sequence.
Additionally, in some embodiments, an instruction can be received at the reprogrammable circuit module from a driver module operatively coupled to the reprogrammable circuit module, such that the search process can be modified based on the instruction. Such a modification can be for example, to reconfigure the reprogrammable circuit module, to update the address for an address translation table (e.g., after a new memory package is coupled to the reprogrammable circuit module), etc. In the example of FIG. 1, after a new memory package is mounted onto the expansion board 100 and operatively coupled to reprogrammable circuit module 120, a driver module at host computer 110 can be configured to send an instruction to reprogrammable circuit module 120, for example, to provide an address for a new address translation table associated with the new memory package.
At 504, a first physical memory address associated with the first logical memory address is retrieved by the reprogrammable circuit module, where the first physical memory address is associated with a memory location at a first memory module coupled to the reprogrammable circuit module by a first data channel. Specifically, the reprogrammable circuit module can be configured to send an address-translation query including the first logical memory address to a first address translation table that includes an entry for the first logical memory address. The first address translation table is stored in a memory module operatively coupled to the reprogrammable circuit module via a data channel. As a result, the first physical memory address, which is associated with the first logical memory address (i.e., the first logical memory address and the first physical memory address are stored as a pair in an entry of the first address translation table), can be retrieved from the first address translation table and sent to the reprogrammable circuit module via the data channel. The first physical memory address identifies a memory location, such as a memory segment unit, in a first memory module that is coupled to the reprogrammable circuit module by a first data channel.
In the example of FIG. 1, reprogrammable circuit module 120 can be configured to send an address-translation query including the first logical memory address L1 to address translation table 180 included in memory module 162 via data channel 131. As a result, a first physical memory address P1, which is associated with the first logical memory address L1 in an entry of address translation table 180, can be retrieved from address translation table 180 and sent back to reprogrammable circuit module 120 via data channel 131. The first physical memory address P1 identifies a memory segment unit in for example, memory module 164, which is coupled to reprogrammable circuit module 120 via data channel 132.
At 506, a second physical memory address associated with the second logical memory address is retrieved by the reprogrammable circuit module, where the second physical memory address is associated with a memory location at a second memory module coupled to the reprogrammable circuit module by a second data channel. Similarly to retrieving the first physical memory address, the reprogrammable circuit module can be configured to send an address-translation query including the second logical memory address to a second address translation table that includes an entry for the second logical memory address. In some embodiments, the second address translation table can be the same as the first address translation table, and thus the second logical memory address can be included in the same address-translation query for the first logical memory address. In some other embodiments, the entry for the second logical memory address is stored in a different address-translation table from that for the first logical memory address, and therefore, a separate address-translation query including the second logical memory address is sent to the second address-translation table, which is probably stored in a different memory module from that for the first address-translation table. As a result, the second physical memory address, which is associated with the second logical memory address (i.e., the second logical memory address and the second physical memory address are stored as a pair in an entry of the second address translation table), can be retrieved from the second address translation table and sent to the reprogrammable circuit module via the data channel. Similar to the first physical memory address, the second physical memory address identifies a memory location, such as a memory segment unit, in a second memory module that is coupled to the reprogrammable circuit module by a second data channel. In some embodiments, the second memory module can be different than the first memory module. In some embodiments, both the first memory module and the second memory module can be included within a common memory package, such as a common DIMM.
In the example of FIG. 1, reprogrammable circuit module 120 can be configured to send an address-translation query including both the first logical memory address L1 and the second logical memory address L2 to address translation table 180 included in memory module 162 via data channel 131. Alternatively, reprogrammable circuit module 120 can be configured to send a different address-translation query including the second logical memory address L2 to a different address translation table (not shown in FIG. 1) included in a different memory module. As a result, in either case, a second physical memory address P2, which is associated with the second logical memory address L2, can be retrieved from the corresponding address translation table and sent to reprogrammable circuit module 120 via a data channel. The second physical memory address P2 identifies a memory segment unit in, for example, memory module 165, which is coupled to reprogrammable circuit module 120 via data channel 133. Furthermore, in the example of FIG. 1, both memory module 164 including a location associated with the first physical memory address P1 and memory module 165 including a location associated with the second physical memory address P2 are included in a common memory package 140, which can be for example, a DIMM.
At 508, the first memory module is accessed, during a first time period, by the reprogrammable circuit module via the first data channel using the first physical memory address. Specifically, based on the first physical memory address retrieved from the address translation table, the reprogrammable circuit module can be configured to locate and access the memory segment unit identified by the first physical memory address, which is included in the first memory module. Particularly, the reprogrammable circuit module can be configured to send a data query to the memory segment unit identified by the first physical memory address via the first data channel. As a result, data can be retrieved, during the first time period, from the memory segment unit identified by the first physical memory address.
In the example of FIG. 1, reprogrammable circuit module 120 can be configured to send a data query to the memory segment unit identified by the first physical memory address P1, which is included in memory module 164, via data channel 132. As a result, data can be retrieved, during a first time period, from the memory segment unit identified by the first physical memory address P1 in memory module 164, via data channel 132.
At 510, the second memory module is accessed, during a second time period overlapping the first time period, by the reprogrammable circuit module via the second data channel using the second physical memory address. Similar to the case for the first physical memory address, the reprogrammable circuit module can be configured to send a data query to the memory segment unit identified by the second physical memory address, which is included in the second memory module, via the second data channel. As a result, data can be retrieved, during the second time period, from the memory segment unit identified by the second physical memory address. Furthermore, because the first memory module and the second memory module are two different memory modules, and the first data channel and the second data channel are two separate data channels, the operation of retrieving data from the first memory module and the operation of retrieving data from the second memory module are independent, therefore can be executed in parallel. Thus, the first time period can be overlapping the second time period.
In the example of FIG. 1, reprogrammable circuit module 120 can be configured to send a data query to the memory segment unit identified by the second physical memory address P2, which is included in memory module 165, via data channel 133. As a result, data can be retrieved, during a second time period, from the memory segment unit identified by the second physical memory address P2 in memory module 165, via data channel 133. Furthermore, the first time period and the second time period can be overlapping.
While various embodiments have been described above, it should be understood that they have been presented by way of example only, not limitation, and various changes in form and details may be made. Any portion of the apparatus and/or methods described herein may be combined in any combination, except mutually exclusive combinations. The embodiments described herein can include various combinations and/or sub-combinations of the functions, components and/or features of the different embodiments described.
While shown and described above with respect to FIGS. 1 and 4 as an address translation table being included in a memory module, in other embodiments, a copy of an address translation table can be stored in a reprogrammable circuit module. In such embodiments, a physical memory address associated with a logical memory address can be retrieved from the copy of the address translation table at the reprogrammable circuit module, without sending a query to the address translation table stored in the memory module. For example, in FIG. 1, a copy of address translation table 180 can be stored at reprogrammable circuit module 120. Thus, reprogrammable circuit module 120 does not need to send a query to address translation table 180 at memory module 162.
While shown and described above with respect to FIGS. 1 and 4 as an expansion board including one reprogrammable circuit module connected to only one memory package, in other embodiments, more than one memory packages can be connected to the reprogrammable circuit module in an expansion board. In some embodiments, for example, a reprogrammable circuit module can be coupled to four memory packages on one expansion board, where each of the memory packages contains 16 memory modules. As a result, in such embodiments, the reprogrammable circuit module can be configured to retrieve data from up to 64 memory modules at the same time, via parallel data channels. In other embodiments, a reprogrammable circuit module can be coupled to any number of memory packages, each of which contains any number of memory modules. As a result, in such embodiments, the reprogrammable circuit module can be configured to retrieve data from any number of memory modules at the same time, via parallel data channels. Furthermore, a SLFM system can be configured to employ parallel processing channels with a large array of multiple reprogrammable circuit modules (e.g., FPGAs), where each of the multiple reprogrammable circuit module has a similar structure and functionality as the reprogrammable circuit module described herein. Inherently, the SLFM system can be scalable by increasing the number of FPGAs and the associated FPGA processing channels.
Some embodiments described herein relate to a computer storage product with a computer-readable medium (also can be referred to as a processor-readable medium) having instructions or computer code thereon for performing various computer-implemented operations. The media and computer code (also can be referred to as code) may be those designed and constructed for the specific purpose or purposes. Examples of computer-readable media include, but are not limited to: magnetic storage media such as hard disks, floppy disks, and magnetic tape; optical storage media such as Compact Disc/Digital Video Discs (CD/DVDs), Compact Disc-Read Only Memories (CD-ROMs), and holographic devices; magneto-optical storage media such as optical disks; carrier wave signal processing modules; and hardware devices that are specially configured to store and execute program code, such as Application-Specific Integrated Circuits (ASICs), Programmable Logic Devices (PLDs), and read-only memory (ROM) and RAM devices.

Claims

1. An apparatus, comprising:

a plurality of memory modules, each memory module from the plurality of memory modules being associated with an address translation table configured to store a plurality of address pairs, each address pair from the plurality of address pairs including (1) a physical memory address associated with a physical location in a memory module from the plurality of memory modules and (2) a logical memory address associated with the physical memory address;

a reprogrammable circuit module configured to execute a search process based at least in part on data stored at the plurality of memory modules, the search process configured to retrieve a first physical memory address associated with a first logical memory address from an address translation table associated with a first memory module from the plurality of memory modules and a second physical memory address associated with a second logical memory address from an address translation table associated with a second memory module from the plurality of memory modules; and

a plurality of data channels, each data channel from the plurality of data channels operably coupling the reprogrammable circuit module to at least one memory module from the plurality of memory modules, the reprogrammable circuit module configured to send, based on the search process, a first query to the first memory module via a first data channel from the plurality of data channels based on the first physical memory address and a second query to the second memory module via a second data channel from the plurality of data channels based on the second memory address.

2. The apparatus of claim 1, wherein each memory module from the plurality of memory modules is included in a dual in-line memory module (DIMM).

3. The apparatus of claim 1, wherein the reprogrammable circuit module is configured to randomly associate the first physical memory address with the first logical memory address.

4. The apparatus of claim 1, wherein the first logical memory address is adjacent to the second logical memory address, the first physical memory address not adjacent to the second physical memory address.

5. The apparatus of claim 1, wherein the reprogrammable circuit module is configured to send the first query at substantially a same time as the second query.

6. The apparatus of claim 1, wherein the reprogrammable circuit module is a Field Programmable Gate Array (FPGA).

7. The apparatus of claim 1, wherein each memory module from the plurality of memory modules is a flash memory module.

8. The apparatus of claim 1, wherein the reprogrammable circuit module is configured to be modified by a driver module.

9. The apparatus of claim 1, wherein the plurality of memory modules are removably coupled to a Peripheral Component Interconnect Express (PCIe) card including the reprogrammable circuit module.

10. A method, comprising:

receiving a query associated with a data lookup, the query including a first logical memory address and a second logical memory address;

retrieving a first physical memory address associated with the first logical memory address, the first physical memory address being associated with a memory location at a first memory module coupled to a reprogrammable circuit module by a first data channel;

retrieving a second physical memory address associated with the second logical memory address, the second physical memory address being associated with a memory location at a second memory module coupled to the reprogrammable circuit module by a second data channel;

accessing, during a first time period, the first memory module via the first data channel using the first physical memory address; and

accessing, at a second time period overlapping the first time period, the second memory module via the second data channel using the second physical memory address.

11. The method of claim 10, wherein the retrieving the first physical memory address includes retrieving the first physical memory address from a first address translation table, the retrieving the second physical memory address includes retrieving the second physical memory address from a second address translation table.

12. The method of claim 10, wherein the retrieving the first physical memory address includes retrieving the first physical memory address from an address translation table stored at the first memory module.

13. The method of claim 10, wherein the first memory module is included within a common dual in-line memory module (DIMM) as the second memory module.

14. The apparatus of claim 10, wherein the first memory module is a flash memory module.

15. The method of claim 10, wherein the accessing the first memory module and the accessing the second memory module are associated with a search process, the method further comprising:

receiving an instruction from a driver associated with the reprogrammable circuit module to modify the search process.

16. An apparatus, comprising:

a first reprogrammable circuit module; and

a memory package including a plurality of memory modules, the memory package being removably coupled to the first reprogrammable circuit module such that the memory package is physically coupled to the first reprogrammable circuit module when in a first configuration and physically coupled to a second reprogrammable circuit module when in a second configuration,

the memory package being operatively coupled to the first reprogrammable circuit module via a plurality of channels when in the first configuration,

at least one memory module from the plurality of memory modules configured to store an address translation table having a plurality of address pairs associated with the plurality of memory modules, each address pair from the plurality of address pairs including (1) a physical memory address associated with a physical location in the plurality of memory modules and (2) a logical memory address associated with the physical memory address,

the first reprogrammable circuit module configured to use the plurality of address pairs to execute a search process via the plurality of channels after the memory package is moved from the second configuration to the first configuration, wherein the search process is substantially the same as a search process executed by the second reprogrammable circuit module when the memory package is in the second configuration.

17. The apparatus of claim 16, wherein the memory package is a dual in-line memory module (DIMM), each memory module from the plurality of memory modules being a flash memory module.

18. The apparatus of claim 16, wherein the first reprogrammable circuit module is a Field Programmable Gate Array (FPGA).

19. The apparatus of claim 16, wherein the search process executed by the first reprogrammable circuit module is configured to retrieve a physical memory address associated with a received logical memory address using the address translation table.

20. The apparatus of claim 16, wherein the first reprogrammable circuit module is configured to send a first query to a first memory module from the plurality of memory modules during a first time period, the first reprogrammable circuit module configured to send a second query to a second memory module from the plurality of memory modules during a second time period overlapping the first time period.