[發明專利]基于增廣立方體網絡的完全二叉樹的嵌入方法

在審

• 申請號: 202010000785.8
• 申請日: 2020-01-02
• 公開（公告）號: CN111143957A
• 公開（公告）日: 2020-05-12
• 發明（設計）人: 徐喜榮;郭靜;王子鳴;李欣子
• 申請（專利權）人: 大連理工大學
• 主分類號: G06F30/18
• 分類號: G06F30/18
• 代理公司: 大連理工大學專利中心 21200
• 代理人: 梅洪玉;劉秋彤

本發明公開了基于增廣立方體網絡的完全二叉樹的嵌入方法，屬于圖嵌入領域。通過計算機搜索得到低維時可嵌入的完全二叉樹，并在此基礎上歸納出高維時可嵌入的完全二叉樹的結構特點，找到遞歸構造完全二叉樹的方法，最終證明完全二叉樹能以擴張1、膨脹1嵌入增廣立方體網絡中。本發明對互連網絡的設計、網絡性能的定量分析和評估有重要的理論指導作用。

技術領域

本發明涉及一種基于增廣立方體網絡的完全二叉樹的嵌入方法，屬于圖嵌入技術領域。

背景技術

近年來，在科學與工程應用、商業應用、國防安全等領域，海量數據的處理和復雜問題的解決對計算能力的要求日益提高。航空航天、石油勘探、車船設計、動漫制作、新藥研發、生物信息、氣候模擬和大型事務處理等許多具體應用均對計算性能提出了極高的需求。隨著晶體管制造工藝已接近原子等級，提高單個處理器的運行速度和性能變得越來越困難。具有多處理器的并行計算機的出現打破了單個處理器的性能瓶頸，從而可以滿足人們對計算機處理速度和性能不斷增長的需求，為實現高性能計算提供了有效的解決方案。

高性能計算被定義為并行計算機上所進行的大量、快速、高效的計算。從普通意義上講，它等同于并行計算或超級計算?；ミB網絡是并行計算系統中多個處理器(處理機)單元之間，處理器(處理機)單元與內存單元之間傳輸數據的機制，并行計算機系統中結點之間的連接方式可以由互連網絡的拓撲結構來定義，并行計算機網絡的帶寬、傳輸延遲、可擴展性、可靠性和對算法的適應性等方面的性能也在很大程度上取決于互連網絡的拓撲結構。

超立方體網絡作為互連網絡典型代表，具有許多優越的性質，例如低直徑、高連通性、對稱性、正則性和良好的可嵌入性等。n維增廣立方體網絡是超立方體的變型，有著比超立方體更優越的性質，n維增廣立方體網絡是(2n-1)-正則、(2n-1)-連通、點可遷的，能較好地滿足網絡設計基本原則的大部分要求，所以它成為并行處理和并行計算機系統的拓撲結構之一。

圖嵌入在并行計算等領域已經得到了廣泛應用，樹、圈、路徑、網孔等是并行計算中使用最為廣泛的互連網絡結構，并且它們代表了許多并行算法的任務圖。完全二叉樹是效率很高的數據結構，常用于模擬并行計算中的常用網絡。被模擬的互連網絡結構作為“客圖”嵌入到另一種互連網絡結構(“主圖”)中。最理想的嵌入是當客圖作為某個并行算法的任務圖時，主圖上能夠取得和在客圖上相同的算法運行速度。在任務分配方面，安排子任務在一個給定的多處理器網絡上執行的問題也可以歸結為圖的嵌入問題。在保證系統設備均能正常運轉的前提下，一個算法能運行于某個計算機系統當且僅當該計算機系統的網絡拓撲上能夠嵌入該算法的通信模式。此外，完全二叉樹的嵌入還有其他若干方面的應用。

因此，將常用的完全二叉樹作為客圖嵌入超立方體及其變型網絡一直是國內外學者關注的重要研究內容，研究增廣立方體網絡上的完全二叉樹的嵌入方法具有重要意義。

發明內容

根據目前的研究發展現狀來看，基于增廣立方體網絡的完全二叉樹的嵌入方法還未提出，在其他超立方體變型網絡上完全二叉樹的嵌入性能仍有提升空間，本發明提供了基于增廣立方體網絡的完全二叉樹的嵌入方法，并且該方法具有優越的嵌入性能。

本發明的技術方案是：在n維增廣立方體AQ_n中，能以擴張1、膨脹1嵌入一棵具有2ⁿ個結點的完全二叉樹CBT_n。

因為增廣立方體AQ_n具有點可遷性，所以在其上的完全二叉樹嵌入以0ⁿ(即n位均為0)節點為根節點，嵌入方法如下：

(1)當n≤4時，通過計算機搜索直接給出可以嵌入到AQ_n中的CBT_n。

圖1、2、3分別是n＝2、3、4時可嵌入到AQ_n中的完全二叉樹CBT_n，如圖所示，其擴張為1、膨脹為1。