Patent Description:
One increasing popular form of networking may generally be referred to as virtual computing systems, which can use protocols such as Remote Desktop Protocol (RDP), Independent Computing Architecture (ICA), and others to share a desktop and other applications with a remote client over a remote session. Such computing systems typically transmit the keyboard presses and mouse clicks or selections from the client to a server, relaying the screen updates back in the other direction over a network connection (e.g., the INTERNET). As such, the user has the experience as if their machine is operating as part of a LAN, when in reality the client device is only sent screenshots of the applications as they appear on the server side.

Compression algorithms are important to reducing the bandwidth used by a remote session to levels that make transmission over LANs, wireless LANs (wLANs) and WANs. These compression algorithms trade processing time on a server in exchange for a lower bandwidth required for the session.

Too high an amount of processing time can inhibit scalability of the server as well as increase the time required to encode a frame, which reduces the overall framerate (FPS) of the remote session. A low FPS negatively impacts the user experience because the session may appeal jerky and feel unresponsive.

Present encoding systems are lacking in ways to take advantage of the multiple processors or processing cores found in many contemporary computers. This lack of maximization of processing resources causes compression time to be higher than it could be.

<CIT> relates to a compression coding apparatus for moving picture data. A moving picture compression coding apparatus includes a region segmentation unit, a plurality of encoding units, an encoded-data combining unit, and a coding control unit. The region segmentation unit is configured to horizontally divide a screen constituting moving picture data into at least three regions. The plurality of encoding units are configured to encode the moving picture data for each of the regions to form encoded data elements, a number of the encoding units being smaller than a number of the regions. The encoding control enables the continuity between the quantization step size in the second area located in the vicinity of the center of the screen and that in the third area, which is adjacent to the second area, to be ensured. Accordingly, the continuity of image quality in the vicinity of the center of the screen, where differences in image quality are prone to being visually recognized, can be ensured.

<CIT> relates to a distributed decoding technology using a multi-core processor which can properly distribute a decoding processing to a plurality of cores of a multi-core processor such that computing power of each core can be effectively utilized. A distributed decoding technology is provided which can effectively divide the decoding processing of MPEG data into a plurality of decoding threads for the plurality of cores.

<CIT> relates to an efficient architecture for a host or server system in a multi-user computer system including one or more Remote Terminals capable of interactive graphics and video. The host computer system generally manages applications and performs server based computing. Each RT has its own keyboard, mouse and display and possibly other peripheral devices. The RTs provide individual users with access to the applications on the server as well as a rich graphical user interface. The host system includes an auxiliary processor referred to as a Terminal Services Accelerator (TSA) that offloads the computational tasks of managing a remote graphics protocol for each RT. The TSA allows a multi-user host computer to economically scale to adaptively support numerous and different RTs that may be networked over a variety of different bandwidth solutions.

It is the object of the present invention to improve compression speed for images on a system with a plurality of processors.

In an embodiment, the resources of multiple processors may be taken advantage of through use of a multi-processor (or core) work manager that allocates a physical central processing unit (CPU) thread per core. An image that is to be encoded is divided into a series of slices - rectangular strips that are of the same width as the image. The work manager dynamically balances and allocates work to available cores and collects completion notifications to allow the final compressed images slices to be re-assembled into a coherent compressed image. The work manager dispatches slices to available processors, such as dispatching a slice to the first processor available. The processor to which the slice is dispatched independently compresses the slice. The work manager receives completion notifications for each slice from each respective core and assembles those compressed slices into the compressed image.

By leveraging multiple processors or cores, compression speed is increased. Cache thrashing is reduced by dividing the image and allocating slices of the image to different cores. Various techniques are available for dynamically allocating compression workload of slices to different processors. Corresponding techniques may be implemented to decompress the compressed image.

It can be appreciated by one of skill in the art that one or more various aspects of the disclosure may include but are not limited to circuitry and/or programming for effecting the herein-referenced aspects of the present disclosure; the circuitry and/or programming can be virtually any combination of hardware, software, and/or firmware configured to effect the herein-referenced aspects depending upon the design choices of the system designer.

The foregoing is a summary and thus contains, by necessity, simplifications, generalizations and omissions of detail. Those skilled in the art will appreciate that the summary is illustrative only and is not intended to be in any way limiting.

The systems, methods, and computer readable media in accordance with this specification are further described with reference to the accompanying drawings in which:.

<FIG> is a block diagram of a general purpose computing device in which the techniques described herein may be employed. The computing system environment <NUM> is only one example of a suitable computing environment and is not intended to suggest any limitation as to the scope of use or functionality of the presently disclosed subject matter. Neither should the computing environment <NUM> be interpreted as having any dependency or requirement relating to any one or combination of components illustrated in the exemplary operating environment <NUM>. In some embodiments the various depicted computing elements may include circuitry configured to instantiate specific aspects of the present disclosure. For example, the term circuitry used in the disclosure can include specialized hardware components configured to perform function(s) by firmware or switches. In other examples embodiments the term circuitry can include a general purpose processing unit, memory, etc., configured by software instructions that embody logic operable to perform function(s). In example embodiments where circuitry includes a combination of hardware and software, an implementer may write source code embodying logic and the source code can be compiled into machine readable code that can be processed by the general purpose processing unit. Since one skilled in the art can appreciate that the state of the art has evolved to a point where there is little difference between hardware, software, or a combination of hardware/software, the selection of hardware versus software to effectuate specific functions is a design choice left to an implementer. More specifically, one of skill in the art can appreciate that a software process can be transformed into an equivalent hardware structure, and a hardware structure can itself be transformed into an equivalent software process. Thus, the selection of a hardware implementation versus a software implementation is one of design choice and left to the implementer.

The system memory <NUM> includes computer storage media in the form of volatile and/or nonvolatile memory such as read only memory (ROM) <NUM> and random access memory.

(RAM) <NUM>.

The computer <NUM> may also include other removable/non-removable, volatile/nonvolatile computer storage media. By way of example only, <FIG> illustrates a hard disk drive <NUM> that reads from or writes to non-removable, nonvolatile magnetic media, a magnetic disk drive <NUM> that reads from or writes to a removable, nonvolatile magnetic disk <NUM>, and an optical disk drive <NUM> that reads from or writes to a removable, nonvolatile optical disk <NUM> such as a CD ROM or other optical media. Other removable/non-removable, volatile/nonvolatile computer storage media that can be used in the exemplary operating environment include, but are not limited to, magnetic tape cassettes, flash memory cards, digital versatile disks, digital video tape, solid state RAM, solid state ROM, and the like. The hard disk drive <NUM> is typically connected to the system bus <NUM> through an non-removable memory interface such as interface <NUM>, and magnetic disk drive <NUM> and optical disk drive <NUM> are typically connected to the system bus <NUM> by a removable memory interface, such as interface <NUM>.

Operating system <NUM>, application programs <NUM>, other program modules <NUM>, and program data <NUM> are given different numbers here to illustrate that, at a minimum, they are different copies. A user may enter commands and information into the computer <NUM> through input devices such as a keyboard <NUM> and pointing device <NUM>, commonly referred to as a mouse, trackball or touch pad. Other input devices (not shown) may include a microphone, joystick, game pad, satellite dish, scanner, or the like. These and other input devices are often connected to the processing unit <NUM> through a user input interface <NUM> that is coupled to the system bus, but may be connected by other interface and bus structures, such as a parallel port, game port or a universal serial bus (USB). A monitor <NUM> or other type of display device is also connected to the system bus <NUM> via an interface, such as a video interface <NUM>. In addition to the monitor, computers may also include other peripheral output devices such as speakers <NUM> and printer <NUM>, which may be connected through a output peripheral interface <NUM>.

The computer <NUM> may operate in a networked environment using logical connections to one or more remote computers, such as a remote computer <NUM>. The remote computer <NUM> may be a personal computer, a server, a router, a network PC, a peer device or other common network node, and typically includes many or all of the elements described above relative to the computer <NUM>, although only a memory storage device <NUM> has been illustrated in <FIG>. The logical connections depicted in <FIG> include a local area network (LAN) <NUM> and a wide area network (WAN) <NUM>, but may also include other networks. Such networking environments are commonplace in offices, enterprise-wide computer networks, intranets and the Internet.

The modem <NUM>, which may be internal or external, may be connected to the system bus <NUM> via the user input interface <NUM>, or other appropriate mechanism. In a networked environment, program modules depicted relative to the computer <NUM>, or portions thereof, may be stored in the remote memory storage device. By way of example, and not limitation, <FIG> illustrates remote application programs <NUM> as residing on memory device <NUM>. It will be appreciated that the network connections shown are exemplary and other means of establishing a communications link between the computers may be used.

Referring now to <FIG>, it generally illustrates an example environment wherein aspects of the present disclosure can be implemented. One skilled in the art can appreciate that the example elements depicted by <FIG> provide an operational framework for describing the present disclosure. Accordingly, in some embodiments the physical layout of the environment may be different depending on different implementation schemes. Thus the example operational framework is to be treated as illustrative only and in no way limit the scope of the claims. One skilled in the art can also appreciate that the following discussion is introductory and the elements depicted by <FIG> are described in more detail within the discussion of the operational procedures of <FIG> through FIG.

Generally, <FIG> depicts a high level overview of a terminal server environment that can be configured to include aspects of the present disclosure. In reference to the figure, a server <NUM> is depicted that can include circuitry configured to effectuate a terminal server and for example, three example clients <NUM>, <NUM>, and <NUM> (while three clients are depicted the server <NUM> in embodiments can service more or less clients). The example clients <NUM>-<NUM> can include computer terminals effectuated by hardware configured to direct user input to the server <NUM> and display user interface information generated by the server <NUM>. In other embodiments, clients <NUM>-<NUM> can be computers that include similar elements as those of computer <NUM> <FIG>. In these example embodiments, clients <NUM>-<NUM> can include circuitry configured to effect operating systems and circuitry configured to emulate the functionality of terminals. In these examples one skilled in the art can appreciate that the circuitry configured to effectuate the operating systems can also include the circuitry configured to emulate terminals.

In the depicted example, the server <NUM> can be configured to generate one or more sessions for connecting clients <NUM>, <NUM>, and <NUM> such as sessions <NUM> through N (where N is an integer greater than <NUM>). Briefly, a session in example embodiments of the present disclosure can generally include an operational environment that is effectuated by a plurality of subsystems, e.g., software code, that are configured to effectuate an execution environment and interact with a kernel <NUM> of an operating system <NUM>. For example, a session can include a shell and a user interface such as a desktop, the subsystems that track mouse movement within the desktop, the subsystems that translate a mouse click on an icon into commands that effectuate an instance of a program, etc. For example, the session can include an application. In this example while an application is rendered, a desktop environment may still be generated and hidden from the user. The session in this example can include similar subsystems as the session described above. Generally, a session can be generated by the server <NUM> on a user by user basis when, for example, the server <NUM> receives a connection request over a network connection from a client such as client <NUM>. Generally, a connection request can first be handled by the transport logic <NUM> that can, for example, be effectuated by circuitry of the server <NUM>. The transport logic <NUM> can include a network adaptor, firmware, and software that can be configured to listen for connection messages and forward them to the engine <NUM>. As illustrated by <FIG>, when sessions are generated the transport logic <NUM> can include protocol stack instances for each session. Generally, each protocol stack instance can be configured to route user interface output to an associated client and route user input received from the associated client to the appropriate session core <NUM>.

As depicted by <FIG>, during the session generation process the engine <NUM> can be configured to obtain a license for the session. For example, the engine <NUM> can receive a license from the client <NUM> during the session generation process. In other examples, the engine <NUM> can receive a copy of a license from a license database <NUM>. In some examples, the license database <NUM> can include a relational database management program that can be executed on an operating system of a computer such as computer <NUM> of <FIG>. In an example that includes a license database <NUM>, it can store one or more licenses that can be checked out when a client attempts to obtain a session from the server <NUM>. In another example, each license can itself be associated with an account identifier, e.g., a username/password combination, a smartcard identifier, etc., and each license can only be checked out if the correct account identifier is presented. Generally, the number of connections that a server <NUM> can generate can be dependent upon the number of licensees the entity that controls the server <NUM> has purchased from a service provider. If for example, the entity has purchased one license, then the server <NUM> can be configured to only allow one session. In this example if the license is associated with an account identifier, then only a user that presents the correct account identifier can obtain a session.

In some examples, of the present disclosure each license can be validated by a service provider <NUM> before they can be used. For example, the service provider <NUM> can act as a certificate authority that aphorizes and activates licenses and servers. In these examples, the service provider <NUM> can ensure that licenses are not stolen, copied, or pirated. The service provider <NUM> can also ensure that the license are only used by the server <NUM> they are purchased for by storing a copy of the licenses in a database and associating the licenses with server <NUM>.

As illustrated by <FIG>, a configuration manager <NUM> in an example can include computer readable instructions that when executed instantiate a process that can receive a license during the session creation process and determine a service level for a newly spawned session by interfacing with various subsystems such as session manager <NUM>. The session manager <NUM> can be configured to initialize and manage each session by for example, generating a session identifier for a session space; adding the session identifier to a table; assigning memory to the session space; and generating system environment variables and instances of subsystem processes in memory assigned to the session space. As illustrated by <FIG>, in an example the session manager <NUM> can instantiate environment subsystems such as a runtime subsystem <NUM> that can include a kernel mode part such as the session core <NUM>. For example, the environment subsystems can be configured to expose a subset of services to application programs and provide an access point to the kernel <NUM> of the operating system <NUM>. As illustrated by <FIG>, the kernel <NUM> can include a security subsystem <NUM> and a resource manager <NUM>. In an example, the security subsystem <NUM> can enforce security policies of the server <NUM> by, for example, performing run-time object protection. In these examples, the resource manager <NUM> can create and terminate processes and threads in response to requests from the runtime subsystem <NUM>. More specifically, the runtime subsystem <NUM> can request the execution of threads and the session core <NUM> can send requests to the executive of the kernel <NUM> to allocate memory for the threads and schedule time for them to be executed.

Continuing with the description of <FIG>, the session core <NUM> can include a graphics display interface <NUM> (GDI) and an input subsystem <NUM>. The input subsystem <NUM> in an example can be configured to receive user input from a client <NUM> via the protocol stack instance associated with the session and transmit the input to the session core <NUM>. The user input can in some examples include signals indicative of absolute and/or relative mouse movement commands, mouse coordinates, mouse clicks, keyboard signals, joystick movement signals, etc. User input, for example, a mouse double-click on an icon, can be received by the session core <NUM> and the input subsystem <NUM> can be configured to determine that an icon is located at the coordinates associated with the double-click. The input subsystem <NUM> can then be configured to send a notification to the runtime subsystem <NUM> that can execute a process for the application associated with the icon.

In addition to receiving input from a client <NUM>, draw commands can be received from applications and/or a desktop and processed by the GDI <NUM>. The GDI <NUM> in general can include a process that can generate graphical object draw commands. The GDI <NUM> in this example can be configured to pass the commands to the remote display subsystem <NUM> that can instantiate a display driver for the session. In an example the remote display subsystem <NUM> can be configured to include virtual display driver(s) that may not be associated with displays physically attached to the server <NUM>, e.g., the server <NUM> could be running headless. The virtual display driver in this example can be configured to receive the draw commands and transmit them to the client <NUM> via a stack instance associated with the session.

<FIG> illustrates a client <NUM> and server <NUM> communicating via a remote session, wherein the server uses multi-processor compression of images <NUM> that it sends to the client.

Where the client <NUM> and server <NUM> communicate via a remote session that is effectuated by remote server <NUM> on server <NUM> communicating with remote client <NUM> on client <NUM> across communications network <NUM>. The remote client <NUM> sends input commands, such as mouse movement or key strokes to the remote server <NUM>, which interprets them and sends the client <NUM> image data <NUM> corresponding to the result of that input. For instance, the client <NUM> may issue mouse movement and clicks to open a video. The server <NUM> will receive this input information, determine that a video is to be played as a result, and send the resulting images <NUM>, and possibly audio, that corresponds to that video being played to the client <NUM> for display on display device <NUM>.

The server <NUM> will often compress the images <NUM> that it sends to the client <NUM>, so as to conserve bandwidth. On the present system, the server <NUM> sends each image <NUM> to a work manager <NUM>, which manages the compression of each image <NUM> across each of the multiple processors <NUM> or cores present on the server <NUM>. The work manager <NUM> will receive an image <NUM> and partition it into one or more slices <NUM>. Whereas a typical remote session compression algorithm may operate on tiles (e.g. 64x64 pixel squares) or strips (e.g. 1680x2 pixel rectangles), a slice <NUM> is typically a much larger section of the image <NUM> (e.g. 1680x128 pixels). The slices <NUM> may selected so as to avoid any cache thrashing issues for a processor <NUM>. In the course of compression, a slice <NUM> may be further divided up into tiles or strips, but the slice <NUM> is the unit that is allocated to a processor <NUM>, so all tiles or stripes within a slice <NUM> remain allocated to that core.

The work manager <NUM> maintains a thread associated with each processor <NUM> that it utilizes to compress the image <NUM>. As the work manager <NUM> generates slices <NUM>, it dispatches each one to one of the threads. The work manager <NUM> may use a variety of techniques to maximize the efficiency of thread dispatch, such as by assigning a slice <NUM> to the first available thread, or queuing a plurality of slices <NUM> on a thread, so that the thread never lacks for a slice <NUM> to compress.

When the thread is executed on its corresponding processor <NUM>, the slice <NUM> is then compressed. In an example, the slice <NUM> is compressed via a run-length encoding (RLE) compression scheme. Once the slice <NUM> is compressed, the work manager <NUM> receives an indication of such. When the work manager <NUM> has received an indication that each slice <NUM> in a given image <NUM> is compressed, it provides the compressed image to the remote server <NUM>, and the remote server <NUM> transfers it to the remote client <NUM> across the communications network <NUM>. The remote client <NUM> receives the compressed image, and directs the client <NUM> to display the received image on display device <NUM>.

An indication that a slice <NUM> has been compressed may comprise a pointer to the memory location where the compressed slice <NUM> resides. In this embodiment, the work manager <NUM> may order these pointers, such that the first pointer points to the start of the image, the last pointer points to the end of the image, and any pointers in between are correspondingly ordered.

The slices <NUM> may be completed in any order. It is the work manager <NUM> that receives these slices <NUM> in whatever order and, in an embodiment, builds an ordered list of pointers to compressed output buffers of the compressed slices <NUM>. Once all slices <NUM> for an image have been compressed, the image is considered to be completely compressed.

In an embodiment, the work manager <NUM> may retrieve each compressed slice <NUM> and then store the compressed image (composed of those compressed slices <NUM>) in a contiguous range of memory.

In an embodiment, the assembly of the compressed image from the compressed slices <NUM> is performed by the client. The server sends the client each compressed slice <NUM> along with some indication both of which image it belongs to and where it belongs within the image, and the client assembles the image from that information. In an embodiment, the server may send the client slices <NUM> from multiple images interleaved, so the indication for each slice <NUM> may comprise both which image it belongs to and which part of the image it is (e.g. the second of five total slices <NUM> for image <NUM>).

The remote server may be synchronous. After it dispatches an image to the work manager <NUM>, it blocks synchronously, waiting for the image to be compressed and to receive the output of the compressed image.

The remote server may be asynchronous. The remote server dispatches an image to the work manager <NUM> and then immediately does further processing, such as parsing received client input or generating a second image for the work manager <NUM> to compress. It later accepts an asynchronous completion notification from the work manager <NUM> comprising an indication that the image has been compressed or the compressed image itself.

<FIG> illustrates exemplary operational procedures for compressing an image on a multi-processor system for transmission via a remote session. A multi-processor system may have a plurality of processing cores or a plurality of discrete processors. In an embodiment, the image comprises a remote session frame, such as an application window or an entire desktop, which may include application windows. In an embodiment, the image comprises a bitmap. In an embodiment, image has a width and a width of each tile is equal to the width of the image.

Operation <NUM> depicts dividing the image into a plurality of slices. In an embodiment, the image is rectangular and each slice is rectangular as well, and has the same horizontal dimension - or width - as the image.

Operation <NUM> depicts for each of at least two processors, associating a thread per processor. A work manager may maintain a thread for each processor that it utilizes in compressing images.

Operation <NUM> depicts assigning each slice to an associated thread. The work manager may use a variety of techniques to maximize the available processor resources. For instance, assigning a slice to an associated thread comprises assigning a slice to an associated thread corresponding to a processor that has unused processing resources.

Operation <NUM> depicts for each slice, receiving an indication that the slice has been processed. For instance, an indication that the slice has been processed comprises a pointer to a corresponding compressed output buffer.

Operation <NUM> depicts assembling the slices into a second image, the second image corresponding to the image being compressed.

Claim 1:
A method for compressing a plurality of images (<NUM>) on a system (<NUM>) with a plurality of processors comprising:
dividing (<NUM>) each image of the plurality of images into a plurality of slices (<NUM>);
for each of at least two processors (<NUM>), associating (<NUM>) a thread per processor;
assigning (<NUM>) each slice to an associated thread;
for each slice, when the associated thread is executed on its corresponding processor, compressing the slice; and
once a slice is compressed, sending the compressed slice along with an indication of which image it belongs to and where it belongs to within the image from a server of the system to a client.