{"id":{"repo_id":"njit","oai_identifier":"oai:digitalcommons.njit.edu:theses-1445"},"canonical_url":"https://search.dev.ndltd.org/etd/njit/oai:digitalcommons.njit.edu:theses-1445","repository":{"repo_id":"njit","name":"NJIT","base_url":"https://digitalcommons.njit.edu/do/oai/"},"display":{"title":"FPGA-based implementation of parallel graph partitioning","abstract":"Graph partitioning is a very important application that can be found in numerous areas, from finite element methods to data processing and VLSI circuit design. Many algorithms have been developed to solve this problem. Of special interest is multilevel graph partitioning that provides a very efficient solution. This method can also be parallelized and implemented on various multiprocessor architectures. Unfortunately, the target of such implementations is often unavailable high-end multiprocessor systems. Here a parallel version of this method for an in-house developed multiprocessor system is implemented on an FPGA. The system designed provides a cost-effective solution. The design is based on two Altera soft IP Nios processors. They are synchronized using shared locks. Also, they communicate information by writing messages into buffers. These buffers are also implemented with shared memory. The design was tested for various graph sizes. The speedup was not attractive for the small graphs but becomes much better as the size of the graph increases. A speedup up to 22% was achieved compared to the single processor design. Larger graphs could yield better speedups. The quality of the partitions produced was also close to the numbers achieved by a single processor. Balance constraints were forced on the partitions and the variations were within 2% of the optimal ones.","abstract_html":"Graph partitioning is a very important application that can be found in numerous areas, from finite element methods to data processing and VLSI circuit design. Many algorithms have been developed to solve this problem. Of special interest is multilevel graph partitioning that provides a very efficient solution. This method can also be parallelized and implemented on various multiprocessor architectures. Unfortunately, the target of such implementations is often unavailable high-end multiprocessor systems. Here a parallel version of this method for an in-house developed multiprocessor system is implemented on an FPGA. The system designed provides a cost-effective solution. The design is based on two Altera soft IP Nios processors. They are synchronized using shared locks. Also, they communicate information by writing messages into buffers. These buffers are also implemented with shared memory. The design was tested for various graph sizes. The speedup was not attractive for the small graphs but becomes much better as the size of the graph increases. A speedup up to 22% was achieved compared to the single processor design. Larger graphs could yield better speedups. The quality of the partitions produced was also close to the numbers achieved by a single processor. Balance constraints were forced on the partitions and the variations were within 2% of the optimal ones.","abstract_has_math":false,"creators":["Kharashgeh, Mohammad"],"institution":null,"degree_name":"Master of Science in Computer Engineering - (M.S.)","degree_level":null,"degree_discipline":"Electrical and Computer Engineering","degree_department":null,"school":null,"contributors":["Sotirios Ziavras","Edwin Hou","Jie Hu"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2006,"date_issued":"2006-08-31T07:00:00Z","date_published":"2006-08-31T07:00:00Z","updated_at":"2026-07-24T03:23:22Z","subjects":["Graph partitioning","Computer Engineering"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.njit.edu/theses/446","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Sotirios Ziavras","Edwin Hou","Jie Hu"]},{"key":"dc:creator","label":"Author","values":["Kharashgeh, Mohammad"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical and Computer Engineering"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science in Computer Engineering - (M.S.)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Graph partitioning","Computer Engineering"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.njit.edu/theses/446"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Graph partitioning is a very important application that can be found in numerous areas, from finite element methods to data processing and VLSI circuit design. Many algorithms have been developed to solve this problem. Of special interest is multilevel graph partitioning that provides a very efficient solution. This method can also be parallelized and implemented on various multiprocessor architectures. Unfortunately, the target of such implementations is often unavailable high-end multiprocessor systems. Here a parallel version of this method for an in-house developed multiprocessor system is implemented on an FPGA. The system designed provides a cost-effective solution. The design is based on two Altera soft IP Nios processors. They are synchronized using shared locks. Also, they communicate information by writing messages into buffers. These buffers are also implemented with shared memory. The design was tested for various graph sizes. The speedup was not attractive for the small graphs but becomes much better as the size of the graph increases. A speedup up to 22% was achieved compared to the single processor design. Larger graphs could yield better speedups. The quality of the partitions produced was also close to the numbers achieved by a single processor. Balance constraints were forced on the partitions and the variations were within 2% of the optimal ones."]},{"key":"dc:title","label":"Title","values":["FPGA-based implementation of parallel graph partitioning"]}]}],"canonical_facts":{"dc:contributor":["Sotirios Ziavras","Edwin Hou","Jie Hu"],"dc:creator":["Kharashgeh, Mohammad"],"dc:description.abstract":["Graph partitioning is a very important application that can be found in numerous areas, from finite element methods to data processing and VLSI circuit design. Many algorithms have been developed to solve this problem. Of special interest is multilevel graph partitioning that provides a very efficient solution. This method can also be parallelized and implemented on various multiprocessor architectures. Unfortunately, the target of such implementations is often unavailable high-end multiprocessor systems. Here a parallel version of this method for an in-house developed multiprocessor system is implemented on an FPGA. The system designed provides a cost-effective solution. The design is based on two Altera soft IP Nios processors. They are synchronized using shared locks. Also, they communicate information by writing messages into buffers. These buffers are also implemented with shared memory. The design was tested for various graph sizes. The speedup was not attractive for the small graphs but becomes much better as the size of the graph increases. A speedup up to 22% was achieved compared to the single processor design. Larger graphs could yield better speedups. The quality of the partitions produced was also close to the numbers achieved by a single processor. Balance constraints were forced on the partitions and the variations were within 2% of the optimal ones."],"dc:identifier":["https://digitalcommons.njit.edu/theses/446"],"dc:subject":["Graph partitioning","Computer Engineering"],"dc:title":["FPGA-based implementation of parallel graph partitioning"],"dc:type":["Thesis"],"thesis:degree_discipline":["Electrical and Computer Engineering"],"thesis:degree_name":["Master of Science in Computer Engineering - (M.S.)"]},"updated_at":"2026-07-24T03:23:22Z"}