Fast Optimal Replica Placement with Exhaustive Search Using Dynamically Reconfigurable Processor
This paper proposes a new replica placement algorithm that expands the exhaustive search limit with reasonable calculation time. It combines a new type of parallel data-flow processor with an architecture tuned for fast calculation. The replica placement problem is to find a replica-server set satis...
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2011-01-01
|
| Series: | Journal of Computer Networks and Communications |
| Online Access: | http://dx.doi.org/10.1155/2011/707592 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832565567402278912 |
|---|---|
| author | Hidetoshi Takeshita Sho Shimizu Hiroyuki Ishikawa Akifumi Watanabe Yutaka Arakawa Naoaki Yamanaka Kosuke Shiba |
| author_facet | Hidetoshi Takeshita Sho Shimizu Hiroyuki Ishikawa Akifumi Watanabe Yutaka Arakawa Naoaki Yamanaka Kosuke Shiba |
| author_sort | Hidetoshi Takeshita |
| collection | DOAJ |
| description | This paper proposes a new replica placement algorithm that expands the exhaustive search limit with reasonable calculation time. It combines a new type of parallel data-flow processor with an architecture tuned for fast calculation. The replica placement problem is to find a replica-server set satisfying service constraints in a content delivery network (CDN). It is derived from the set cover problem which is known to be NP-hard. It is impractical to use exhaustive search to obtain optimal replica placement in large-scale networks, because calculation time increases with the number of combinations. To reduce calculation time, heuristic algorithms have been proposed, but it is known that no heuristic algorithm is assured of finding the optimal solution. The proposed algorithm suits parallel processing and pipeline execution and is implemented on DAPDNA-2, a dynamically reconfigurable processor. Experiments show that the proposed algorithm expands the exhaustive search limit by the factor of 18.8 compared to the conventional algorithm search limit running on a Neumann-type processor. |
| format | Article |
| id | doaj-art-292bf83883f944128e9cc00756d358b5 |
| institution | Kabale University |
| issn | 2090-7141 2090-715X |
| language | English |
| publishDate | 2011-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Computer Networks and Communications |
| spelling | doaj-art-292bf83883f944128e9cc00756d358b52025-02-03T01:07:14ZengWileyJournal of Computer Networks and Communications2090-71412090-715X2011-01-01201110.1155/2011/707592707592Fast Optimal Replica Placement with Exhaustive Search Using Dynamically Reconfigurable ProcessorHidetoshi Takeshita0Sho Shimizu1Hiroyuki Ishikawa2Akifumi Watanabe3Yutaka Arakawa4Naoaki Yamanaka5Kosuke Shiba6Department of Information and Computer Science, Faculty of Science and Technology, Keio University, Yokohama, 223-8522, JapanDepartment of Information and Computer Science, Faculty of Science and Technology, Keio University, Yokohama, 223-8522, JapanDepartment of Information and Computer Science, Faculty of Science and Technology, Keio University, Yokohama, 223-8522, JapanIPFlex Inc., Tokyo 141-0021, JapanDepartment of Information and Computer Science, Faculty of Science and Technology, Keio University, Yokohama, 223-8522, JapanDepartment of Information and Computer Science, Faculty of Science and Technology, Keio University, Yokohama, 223-8522, JapanIPFlex Inc., Tokyo 141-0021, JapanThis paper proposes a new replica placement algorithm that expands the exhaustive search limit with reasonable calculation time. It combines a new type of parallel data-flow processor with an architecture tuned for fast calculation. The replica placement problem is to find a replica-server set satisfying service constraints in a content delivery network (CDN). It is derived from the set cover problem which is known to be NP-hard. It is impractical to use exhaustive search to obtain optimal replica placement in large-scale networks, because calculation time increases with the number of combinations. To reduce calculation time, heuristic algorithms have been proposed, but it is known that no heuristic algorithm is assured of finding the optimal solution. The proposed algorithm suits parallel processing and pipeline execution and is implemented on DAPDNA-2, a dynamically reconfigurable processor. Experiments show that the proposed algorithm expands the exhaustive search limit by the factor of 18.8 compared to the conventional algorithm search limit running on a Neumann-type processor.http://dx.doi.org/10.1155/2011/707592 |
| spellingShingle | Hidetoshi Takeshita Sho Shimizu Hiroyuki Ishikawa Akifumi Watanabe Yutaka Arakawa Naoaki Yamanaka Kosuke Shiba Fast Optimal Replica Placement with Exhaustive Search Using Dynamically Reconfigurable Processor Journal of Computer Networks and Communications |
| title | Fast Optimal Replica Placement with Exhaustive Search Using Dynamically Reconfigurable Processor |
| title_full | Fast Optimal Replica Placement with Exhaustive Search Using Dynamically Reconfigurable Processor |
| title_fullStr | Fast Optimal Replica Placement with Exhaustive Search Using Dynamically Reconfigurable Processor |
| title_full_unstemmed | Fast Optimal Replica Placement with Exhaustive Search Using Dynamically Reconfigurable Processor |
| title_short | Fast Optimal Replica Placement with Exhaustive Search Using Dynamically Reconfigurable Processor |
| title_sort | fast optimal replica placement with exhaustive search using dynamically reconfigurable processor |
| url | http://dx.doi.org/10.1155/2011/707592 |
| work_keys_str_mv | AT hidetoshitakeshita fastoptimalreplicaplacementwithexhaustivesearchusingdynamicallyreconfigurableprocessor AT shoshimizu fastoptimalreplicaplacementwithexhaustivesearchusingdynamicallyreconfigurableprocessor AT hiroyukiishikawa fastoptimalreplicaplacementwithexhaustivesearchusingdynamicallyreconfigurableprocessor AT akifumiwatanabe fastoptimalreplicaplacementwithexhaustivesearchusingdynamicallyreconfigurableprocessor AT yutakaarakawa fastoptimalreplicaplacementwithexhaustivesearchusingdynamicallyreconfigurableprocessor AT naoakiyamanaka fastoptimalreplicaplacementwithexhaustivesearchusingdynamicallyreconfigurableprocessor AT kosukeshiba fastoptimalreplicaplacementwithexhaustivesearchusingdynamicallyreconfigurableprocessor |