Back when I competed in programming contests, problems would be wrapped up in “real-world” stories, with the goal of making the problem easier to comprehend and more digestible for larger audiences. Following such tradition (hopefully), I present a story about a common problem developers deal with here at Acceleware.
In recent years, AxIsland has become quite a tourist destination, and hotel companies have been flourishing. Sixteen different hotel chains exist on the island, each with multiple accommodation offerings and courtesy taxi service. The high cost of beach property forced the local airport onto a nearby island, thus arriving tourists must first hop onto a taxi vehicle (run by their choice of hotel chain) before taking a small ferry across to AxIsland. The ferry service is a joint service run by the sixteen hotel chains, and has exactly sixteen spots for taxi-vehicles, reserved exclusively for its respective hotel chain. It used to be that single-passenger taxi-cabs were the only taxi-vehicles on AxIsland, but recently taxi-vans capable of holding up to sixteen passengers (all headed to the same hotel) were introduced to accommodate large families and business-retreat visitors. Unfortunately, the introduction of taxi-vans also introduced logistical problems. The ferry can still carry sixteen taxi-vehicles at once, however due to the ferry’s size and slot restrictions there is only room for at most one taxi-van. Due to this constraint, hotel-chains began bickering over who could operate the taxi-van, before it was finally decided that taxi-van destination hotel would be that of the first tourist waiting in line for transportation. This solution is far from ideal, and can lead to tourists sitting around waiting a long time for their turn on the ferry.
Given a list of tourists and their destination hotels, your job is to assign them to one of the daily flights headed to AxIsland in such a way that minimizes the worse-case total number of ferry transfers needed. (Worst-case due to the fact that you have no control over which tourist gets in line for the ferry first).
In the examples below, sixteen passengers have lined up for the ferry. Color is used to symbolize the hotel chain they are staying at, while the shape represents the destination hotel. The ferry has 16 smaller squares for taxi-cabs with their respective hotel-chain color pattern, along with one large square to accommodate a single taxi-van. In the first configuration, two ferry transfers are required. The second configuration has the same passengers as the first, but due to the way they lined up for the ferry, it will take 4 transfers.
Start:
Start:
Believe it or not, this convoluted ferry system is a common problem that developers here at Acceleware have encountered. When dealing with high-performance computing, the rate at which data can be transferred is often a performance bottleneck, similar to the way the ferry makes passengers wait. In fact, AxIsland's ferry system is analogous to NVIDIA CUDA's shared memory system. Shared memory is on-chip, meaning that accessing data from shared memory is much faster than other memory locations (think how long it would take tourists to swim to AxIsland). Data can be transferred quickly in parallel because memory addresses (hotels) are split into sixteen distinct memory banks (hotel companies), all of which can be serviced by a single transaction (ferry ride). One "random" memory address is selected to be broadcast (taxi-van), while each remaining memory bank selects one of the remaining available addresses it is responsible for (taxi-cab). This continues until all memory addresses are dealt with. If N such transactions are required to service a set of memory requests, then it is known in the CUDA literature as an N-way bank conflict (N-ferry transfers).
It's not always possible to eliminate bank conflicts, but understanding the hardware mechanism promotes and accounting for it certainly helps performance - a fact we took advantage of in our recently completed Saudi Aramco project.
Written by guest blogger and Acceleware Software Developer Gilbert Lee.
