Patent Description:
Computing systems are often virtualized, or emulated, to enable simulation, testing, and development of that computing environment on a host computer, such as a desktop personal computer. Virtualization refers to the imitation of a given unit of hardware by a software program, such as a virtual machine (VM), executing on a local, or host, computer via a hypervisor. In some instances, VMs execute without a hypervisor. Virtualization enables development, testing, and execution of target software without the need for a complete target computing system, which may have limited availability.

At least some of those computing systems utilize a multicore processor and multi-thread, or parallel, processing of target software. In some instances, multiprocessing hardware is used instead of, or in combination with, multicore processors to provide multiple processor cores for parallel execution. When that target software includes multiple threads, tasks, and/or processes intended to execute in parallel on a multicore processor or on multiple processors, execution of that target software and, more specifically, the multiple threads on multiple virtual cores demands that the threads be synchronized or coordinated in some manner. One solution is to execute the threads serially in an incremental manner, e.g., from interrupt to interrupt. However, this results in degradation of the VM's performance, particularly as the number of threads and target processing cores increases. Another solution is to synchronize virtual time, i.e., the timing within the VM, with "wall clock" time, i.e., actual time in the physical world, however, if the virtualized system cannot execute software fast enough to match wall clock time, then it is often not possible to achieve synchronization, which can be the case when processor emulation is used in the virtual machine. In other scenarios, it is desirable to run faster than wall clock time, and in this scenario wall clock time cannot easily be used as a time source and a synchronized virtual time source is required. Moreover, these conventional solutions result in an inability to produce VMs that match the desired performance characteristics for multicore applications using VMs such as test environments and trainers. Accordingly, improved timekeeping for VMs having multiple virtual processing cores is desired.

For the purpose of this disclosure, the terms "virtualization" and "emulation" are used interchangeably to refer to a VM where any aspect of target hardware is being emulated, although the host computer may incorporate one or more other aspect of target hardware.

Document <CIT>, according to its abstract, states a method of providing virtualization services, computer program(s) executable as a plurality of tasks may be identified, as may task(s) from the plurality of tasks. The computer program(s) may be executed by virtual central processing unit(s) (CPUs) in a virtual machine executed on a host hardware platform and defined to provide a virtualization platform for virtualization of a target hardware platform. This may include the plurality of tasks other than the (identified) task(s) being executed by the virtual CPU(s) in the virtual machine executed on CPU(s) of the host hardware platform, and at least partially in parallel with these tasks, executing the task(s) on additional CPU(s) of the host hardware platform. The target hardware platform may include CPU(s) for execution the plurality of tasks no greater in number than the CPU(s) of the host hardware platform on which the plurality of tasks other than the task(s) are executed.

The scientific article by <NPL>, states a network emulator enable rapid prototyping and testing of applications.

Document <CIT>, according to its abstract, states a computing system in which a software component executing on a platform can obtain state information about a component supported by the platform through the use of a shared memory page. State information may be supplied by the platform, but any state translation information needed to map the state information as supplied to a format as used may be provided through the shared page. In a virtualized environment, the state translation information can be used to map the value of a virtual timer counter or other component from a value provided by a virtual processor to a normalized reference time that will yield the same result, regardless of whether the software component is migrated to or from another virtual processor. Use of a shared page avoids the inefficiency of an intercept into a virtualized environment, or a system calls in native mode operation.

The claimed invention is set out in the appended set of claims.

Corresponding reference characters indicate corresponding parts throughout the several views of the drawings. Although specific features of various examples may be shown in some drawings and not in others, this is for convenience only. Any feature of any drawing may be referenced and/or claimed in combination with any feature of any other drawing.

The host computer disclosed provides a virtual time object stored in a memory section such that it can be used in the virtualization layer by multiple virtualized cores of the VM. The virtual time object may include, for example, a variable, data structure, or class in which virtual time can be stored. When executing target code having multiple threads executed in parallel, the VM designates one virtual core as the timekeeper to increment the virtual time object by a count of its instructions executed, and then the VM moves the designation to another virtual core that, likewise, increments the virtual time object by its count of its instructions executed. The designation may include a variable, data structure, class, Boolean, flag or other read/write software structure that can identify a given virtual core as the timekeeper. The designation of timekeeper may be moved, for example, in response to detecting an event, such as an interrupt or completion of execution of a translation block of code.

A translation block is created when processor emulation is used within a VM. Translation blocks improve performance of processor emulation. In direct processor emulation (i.e., without translation blocks), every instruction in the target software is encountered logic in the processor emulation, and the VM translates that target software (e.g., assembly or machine code) to host code (e.g., host assembly or machine code). Translation blocks enable blocks of target software to be translated and cached for future use during execution. This caching is possible because the target software binary does not change and most software is cyclic in nature and only executes a small percentage of all overall code in the binary. Translation blocks are variable in length and are designed to end at some transition in the code, such as, for example, a branch statement or a context switch. These transitions in the code cause the translation block being worked on in the processor emulator to be moved out and a new translation block loaded into the processor emulator. The transition of translation blocks is conceptually similar to context switches.

<FIG> is a block diagram of an example memory structure for a host computer having a host central processing unit (CPU) <NUM>, having one or multiple cores. Referring to the example shown in <FIG>, host CPU <NUM> includes at least two cores including a core <NUM><NUM> and a core <NUM><NUM>. Host CPU <NUM> is configured, or programmed, to execute a VM <NUM> using a virtualization layer <NUM>. VM <NUM> is configured to execute target code, or software, having multiple threads, tasks, and/or processes that may be processed serially or in parallel on a target multicore processor. VM <NUM> includes a virtual multicore processor <NUM> having N virtual cores <NUM>. <FIG> is an example timing diagram <NUM> of serial processing of the multi-threaded target code. <FIG> is an example timing diagram <NUM> of parallel processing of the multi-threaded target code. <FIG> illustrates four threads executing serially on respective virtual cores <NUM>, <NUM>, <NUM>, <NUM>. Sections of code <NUM>, <NUM>, <NUM>, <NUM> in each thread execute sequentially on virtual cores <NUM>, <NUM>, <NUM>, <NUM> over virtual time, which is represented on a virtual time axis <NUM>. Notably, the time required to execute the four threads serially is a factor of four longer than executing the same threads in parallel, as shown in <FIG>. However, timekeeping can simply progress serially with the threads in virtual time.

In <FIG>, timing diagram <NUM> illustrates the same virtual cores <NUM>, <NUM>, <NUM>, <NUM> processing the same target code <NUM>, <NUM>, <NUM>, <NUM> in parallel. Each target code <NUM>, <NUM>, <NUM>, <NUM> include a unique set of executable instructions that vary in the time necessary to process by their respective virtual cores <NUM>, <NUM>, <NUM>, <NUM>. Virtual cores <NUM>, <NUM>, <NUM>, <NUM> process in parallel and track virtual time with a virtual time object, and without synchronizing virtual time with wall-clock time. Because each thread of target code <NUM>, <NUM>, <NUM>, <NUM> is unequal in its time required for execution of instructions, timekeeping is distributed among all virtual cores <NUM>, <NUM>, <NUM>, <NUM>. Notably, parallel-executed threads are often interdependent and must occasionally halt and wait for another thread to catch up or for a shared resource to become available. Although <FIG> illustrates four virtual cores, the disclosed timekeeping method may be embodied in a virtualized multicore processor having any number, N, of virtual cores, i.e., two or more.

Referring to host CPU <NUM> shown in <FIG>, the virtual time object <NUM> is stored in a section of memory accessible by virtualization layer <NUM> for use by all virtual cores <NUM> in VM <NUM>, from virtual core <NUM><NUM> to virtual core N <NUM>. The memory space may include, for example, an address in random access memory (RAM) <NUM>. The target code itself, including its multiple threads, each composed of multiple executable instructions, may also be stored in RAM <NUM>. Alternatively, target code may be stored in another memory space, such as a non-volatile RAM (NVRAM) or a mass storage device.

Alternatively, the memory space storing the virtual time object <NUM> may include an address in a shared cache, such as a layer <NUM> (L3) cache <NUM>. Generally, each host core has one or more dedicated cache memory spaces. The dedicated cache may include, for example, one or more layer <NUM> (L1) cache <NUM> and one or more layer <NUM> (L2) cache <NUM>. Each additional layer of cache memory is generally larger and slower than the next lower level. For example, L1 cache <NUM> is typically the smallest volume of memory, but the fastest. L2 cache <NUM> is typically larger than L1 cache <NUM>, but has slower read and write times. Likewise, L3 cache <NUM> is even larger, but again has slower read and write times. In certain embodiments, one or more of the dedicated cache memories (L1 <NUM> or L2 <NUM>) is incorporated with its corresponding host core, e.g., core <NUM><NUM> or core <NUM><NUM>. In alternative embodiments, the virtual time object <NUM> may be stored in another memory space coupled to the host cores over, for example, a memory bus <NUM>.

For each virtual core <NUM>, for example, virtual core <NUM><NUM> and virtual core N <NUM>, VM <NUM> tracks virtual time by counting the number of emulated instructions executed and then incrementing the virtual time object <NUM>. However, only one virtual core can increment, or advance, the virtual time object <NUM> at a given moment in time, because that one core locks the memory space, e.g., L3 cache <NUM>. Consequently, one or more other virtual cores may stop processing its thread to preserve cache coherency, resulting in degraded performance of virtualized multicore processor <NUM>. As the number of virtual cores increases, cache coherency issues compound. Moreover, one virtual core increments virtual time, because virtual time advances too quickly (e.g., faster than wall-clock time) when all threads increment virtual time. For example, a virtual processor with N cores advances virtual time N-times faster than with a single core or serially executing cores.

The VM <NUM> designates, or assigns a designation to, a first virtual core, e.g., virtual core N <NUM>, to increment the virtual time object <NUM> by its count of the instructions executed in its thread of target code over a first duration. The designation is then moved to another virtual core <NUM> in response to detecting an event that defines an end of the first duration. That virtual core <NUM> then increments the virtual time object <NUM> by its count of instructions executed in its thread of target code over a second duration. All virtual cores otherwise execute their respective threads in parallel and only the designated virtual core increments the virtual time object <NUM>.

The instructions, i.e., the target code, executed in a given thread by a corresponding virtual core may include, for example, a block of assembly language instructions. Those instructions may also include instructions to read the virtual time object <NUM> from time to time, e.g., periodically, which functions to synchronize the multiple threads and their corresponding virtual cores. Alternatively, the VM <NUM> may periodically instruct each virtual core to read the virtual time object <NUM>.

The designation of timekeeper is moved in response to an event, such as an interrupt, the completion of execution of a translation block of instructions, or the halting of the virtual core that holds the designation of timekeeper. The moving designation avoids locking the shared memory space, which can cause one or more virtual cores <NUM> to halt execution. Although processing loads of the virtual cores <NUM> are often unequal, or unbalanced, at a given moment in time, over a longer duration, as each virtual core <NUM> contributes to the incrementing, or advancing of virtual time, the unequal processing loads across the virtual cores <NUM> are smoothed, or tend toward average.

<FIG> is a block diagram of an example host computer <NUM> for emulating a target multicore processor. The target multicore processor is a hardware multi-core processor to be emulated. For example, a computing system, i.e., the target hardware, may utilize a dual-core or quad-core processor. Alternatively, the target multicore processor may include eight or more processing cores. Generally, the target multicore processor includes two or more processing cores. Host computer <NUM> includes host CPU <NUM> coupled to a cache memory <NUM>, and further coupled to RAM <NUM> and host memory <NUM> via a memory bus <NUM>. Cache memory <NUM> and RAM <NUM> are configured to operate with host CPU <NUM> as multicore processor <NUM> operates with RAM <NUM> and the corresponding cache memory shown in <FIG>. More specifically, the virtual time variable is stored in a memory space allocated in RAM <NUM> or in cache memory <NUM>. Host memory <NUM> is a computer-readable memory (e.g., volatile or non-volatile) that includes a memory section storing a VM <NUM>, a section storing an OS <NUM>, a section storing a virtualization layer <NUM>, a section storing target code <NUM>, and a section storing a virtual time object <NUM>, such as a variable, a data structure, or a class. In alternative embodiments, one or more section of host memory <NUM> may be omitted and the data stored remotely. For example, in certain embodiments, target code <NUM> may be stored remotely on a server or mass-storage device, and made available over a network to host CPU <NUM> and VM <NUM>. VM <NUM> includes virtualized multicore processor <NUM>.

Host computer <NUM> also includes host I/O devices <NUM>, which may include, for example, a communication interface such as an Ethernet controller <NUM>, or a peripheral interface for communicating with a host peripheral device <NUM> over a peripheral link <NUM>. Host I/O devices <NUM> may include, for example, a GPU for operating a display peripheral over a display link.

<FIG> is a flow diagram of an example method <NUM> of tracking virtual time in a VM having a virtual multicore processor, such as VM <NUM> and virtualized multicore processor <NUM> shown in <FIG> and <FIG>, respectively. A first virtual core, e.g., virtual core <NUM><NUM>, executes <NUM> a first thread that includes a first plurality of instructions. A second core, e.g., virtual core N <NUM>, executes <NUM> a second thread that includes a second plurality of instructions. A virtual time object <NUM> is stored <NUM> in a section of host memory shared between at least the first and second virtual cores. For example, as shown in <FIG>, the virtual time object <NUM> may be stored in L3 cache <NUM>, which is shared by virtual core <NUM><NUM> and virtual core N <NUM>.

The VM assigns <NUM> a designation to the first virtual core to increment the virtual time object <NUM> by a first count of the first plurality of instructions executed in the first thread over a first duration. The designation is then moved <NUM> to the second virtual core in response to detecting an event that defines an end of the first duration. For example, the event may include an interrupt, the completion of execution of a section of code, e.g., a translation block, and, includes the halting of the first virtual core according to the claimed invention.

The second virtual core then increments <NUM> the virtual time object <NUM> by a second count of the second plurality of instructions executed in the second thread over a second duration. Virtual cores execute in parallel and only one virtual core updates virtual time.

In certain embodiments, method <NUM> includes mapping the shared cache, e.g., L3 cache <NUM>, to a shared cache for a host multicore processor. In certain embodiments, method <NUM> includes reading, by the second virtual core, the virtual time object <NUM> during the first duration. The reading may be by an instruction in the second thread or, alternatively, by instruction from the VM.

An example technical effect of the methods, systems, and apparatus described herein includes at least one of: (a) tracking virtual time in a virtualized multicore processor executing multiple target code threads in parallel; (b) eliminating wall-clock synchronization of virtual time; (c) storing a virtual time object in a shared memory space without disrupting cache coherency; and (d) distributing timekeeping among the multiple virtual cores by moving the timekeeping designation on an event-driven basis.

Some embodiments involve the use of one or more electronic processing or computing devices. As used herein, the terms "processor" and "computer" and related terms, e.g., "processing device," "computing device," and "controller" are not limited to just those integrated circuits referred to in the art as a computer, but broadly refers to a processor, a processing device, a controller, a general purpose central processing unit (CPU), a graphics processing unit (GPU), a microcontroller, a microcomputer, a programmable logic controller (PLC), a reduced instruction set computer (RISC) processor, a field programmable gate array (FPGA), a digital signal processing (DSP) device, an application specific integrated circuit (ASIC), and other programmable circuits or processing devices capable of executing the functions described herein, and these terms are used interchangeably herein. These processing devices are generally "configured" to execute functions by programming or being programmed, or by the provisioning of instructions for execution. The above examples are not intended to limit in any way the definition or meaning of the terms processor, processing device, and related terms.

In the embodiments described herein, memory may include, but is not limited to, a non-transitory computer-readable medium, such as flash memory, a random access memory (RAM), read-only memory (ROM), erasable programmable read-only memory (EPROM), electrically erasable programmable read-only memory (EEPROM), and non-volatile RAM (NVRAM). As used herein, the term "non-transitory computer-readable media" is intended to be representative of any tangible, computer-readable media, including, without limitation, non-transitory computer storage devices, including, without limitation, volatile and non-volatile media, and removable and non-removable media such as a firmware, physical and virtual storage, CD-ROMs, DVDs, and any other digital source such as a network or the Internet, as well as yet to be developed digital means, with the sole exception being a transitory, propagating signal. Alternatively, a floppy disk, a compact disc - read only memory (CD-ROM), a magneto-optical disk (MOD), a digital versatile disc (DVD), or any other computer-based device implemented in any method or technology for short-term and long-term storage of information, such as, computer-readable instructions, data structures, program modules and sub-modules, or other data may also be used. Therefore, the methods described herein may be encoded as executable instructions, e.g., "software" and "firmware," embodied in a non-transitory computer-readable medium. Further, as used herein, the terms "software" and "firmware" are interchangeable, and include any computer program stored in memory for execution by personal computers, workstations, clients and servers. Such instructions, when executed by a processor, cause the processor to perform at least a portion of the methods described herein.

Also, in the embodiments described herein, additional input channels may be, but are not limited to, computer peripherals associated with an operator interface such as a mouse and a keyboard. Alternatively, other computer peripherals may also be used that may include, for example, but not be limited to, a scanner. Furthermore, in some embodiments, additional output channels may include, but not be limited to, an operator interface monitor.

The systems and methods described herein are not limited to the specific embodiments described herein, but rather, components of the systems and/or steps of the methods may be utilized independently and separately from other components and/or steps described herein.

Although specific features of various embodiments of the disclosure may be shown in some drawings and not in others, this is for convenience only. In accordance with the principles of the disclosure, any feature of a drawing may be referenced and/or claimed in combination with any feature of any other drawing.

Claim 1:
A host computer (<NUM>) for virtualizing a target multicore processor, the host computer (<NUM>) comprising:
a host memory (<NUM>) including a first section of memory storing a virtual time object (<NUM>, <NUM>), and a second section storing a virtual machine, VM, (<NUM>, <NUM>), wherein the VM (<NUM>, <NUM>) includes target code (<NUM>) comprising a plurality of threads, wherein each thread includes a plurality of instructions configured to execute on the target multicore processor; and
a host central processing unit, CPU, (<NUM>, <NUM>) configured to execute the VM (<NUM>, <NUM>) to virtualize the target multicore processor, the VM (<NUM>, <NUM>) being configured to:
execute the plurality of threads in parallel on corresponding virtual cores (<NUM>, <NUM>), including a first thread having a first plurality of instructions executing on a first virtual core and a second thread having a second plurality of instructions executing on a second virtual core;
assign a designation to the first virtual core to increment the virtual time object (<NUM>, <NUM>) by a first count of the first plurality of instructions executed in the first thread over a first duration;
move the designation to the second virtual core in response to detecting an event that defines an end of the first duration; and
increment, by the second virtual core, the virtual time object (<NUM>, <NUM>) by a second count of the second plurality of instructions executed in the second thread over a second duration;
wherein the event includes a halting of execution by the first virtual core (<NUM>, <NUM>);
wherein the first section of the host memory (<NUM>) is mapped to a shared cache level (<NUM>) for storing the virtual time object (<NUM>, <NUM>).