Virtual world simulation systems and methods utilizing parallel coprocessors, and computer program products thereof
The current invention provides a virtual world simulation system capable of hosting with massive amount of concurrent players by integrating commodity parallel co-processors into servers. The current invention proposes novel parallel processing algorithms to make use of commodity parallel co-processors like a graphic processing unit (GPU) or any specialized hardware with parallel architecture design like a field-programmable gate array (FPGA), to accelerate virtual world simulation.
1. A method for simulating a virtual world by utilizing a parallel co-processor with a dedicated memory, comprising:
performing a parallel logic processing by said parallel co-processor, wherein said performing said parallel logic processing comprises:
performing a count phase, wherein said performing said counting phase comprises:
determining a first plurality of update counts for a plurality of threads in a counting phase by said parallel co-processor;
storing said first plurality of update counts into said dedicated memory; and
allocating a memory block from said dedicated memory according to said first plurality of update counts for storing a plurality of update vectors without any memory conflict;
performing a storing phase, wherein said performing said storing phase comprises:
writing updates into said memory block;
performing a parallel conflict merge by said parallel co-processor, wherein said performing said parallel conflict merge comprises:
generating a sorted list from said first plurality of update vectors;
generating a first separation list from said sorted list;
generating a first store indices list;
generating a merge list based on said first separation list and said first store indices list; and
performing parallel merge based on said merge list;
performing a parallel range query by said parallel co-processor, wherein said performing said parallel range query comprises:
calculating a plurality of affected buckets based on a second plurality of update vectors, wherein said virtual world is divided into a plurality of buckets, each bucket is a square or a cube with an edge length equal to a visibility range, and each of said plurality of affected buckets is within said visibility range from any of said second plurality of update vectors;
generating a second separation list from said plurality of affected buckets;
generating a second store indices list;
determining a second plurality of update counts based on said plurality of affected buckets;
allocating a second memory block from said dedicated memory according to said second plurality of update counts for storing said plurality of affected buckets.
2. The method for simulating the virtual world as claimed in claim 1 , wherein said parallel co-processor is a graphic processing unit.
3. The method for simulating the virtual world as claimed in claim 1 , wherein said parallel co-processor is a field-programmable gate array (FPGA).
4. The method for simulating the virtual world as claimed in claim 1 , wherein said virtual world is a computer based real-time simulated environment where a first virtual world object interacts with a second virtual world object.
5. The method for simulating the virtual world as claimed in claim 1 , wherein said virtual world is a Massive Multiplayer On-Line Game (MMOG).
6. The method for simulating the virtual world as claimed in claim 1 , wherein said generating said first separation list in performing parallel conflict merge further comprises comparing two adjacent elements in said sorted list.
7. The method for simulating the virtual world as claimed in claim 1 , wherein said allocating said first memory block from said dedicated memory further comprises:
performing a parallel prefix sum on said first plurality of update counts to determine a storage requirement for storing a plurality of update vectors by said parallel co-processor; and
allocating said first memory block according to said storage requirement.
8. The method for simulating the virtual world as claimed in claim 1 , wherein said first plurality of update vectors is identical to said second plurality of update vector.
9. The method for simulating the virtual world as claimed in claim 1 , wherein before calculating said plurality of affected buckets based said second plurality of update vectors, the method further comprises performing a parallel sort on attributes of a plurality of virtual world objects, which are targeted to be updated.
10. The method for simulating the virtual world as claimed in claim 1 , wherein after calculating said plurality of affected buckets based said second plurality of update vectors, the method further comprises performing a parallel sort on attributes of a plurality of virtual world objects, which are targeted to be updated.
11. The method for simulating the virtual world as claimed in claim 1 , wherein said performing a parallel conflict merge by said parallel co-processor further comprises:
generating said first store indices list by performing a parallel prefix sum on said first separation list.