Skip to main content

Chap#10

Network topologies Definition:

Network topologies define how nodes (processors/computers) are interconnected in parallel and distributed systems. The choice of topology affects performance, scalability, and cost.

Key Metrics:

Degree: Number of links per node. (Formula: deg = connections per node)

Example: In a linear array, each node (except ends) has 2 links.


Diameter: Longest shortest path between any two nodes. (Formula: diam = max distance)

Example: Linear array with 8 nodes has diameter 7 (P₀ to P₇).


Bisection Width: Minimum links to cut to split the network into two halves. (Formula: bw = min cuts)

Example: Binary tree has bw=1 (cutting the root disconnects it).4

1. Linear Array

Define:
Nodes are connected one after another in a straight line. Each node (except the ends) connects to two neighbors one on the left and one on the right.

Explanation:
Simple to build and easy to understand, but not efficient for large networks.
Long distance between farthest nodes makes communication slow.
If one node fails, communication might be interrupted.

Example (8 nodes: P₀ to P₇):

  • Degree = 2 (except the first and last nodes, which have 1 connection)

  • Diameter = n - 1 = 7 (distance from P₀ to P₇)

  • Bisection Width = 1 (cutting one middle link splits the network)

2. 2D Mesh / Torus

Define:
Nodes are arranged in a 2D grid like rows and columns.
In a torus, edge nodes are also connected to opposite edges (wrap-around).

Explanation:
More balanced than a linear array.
Better communication efficiency and fault tolerance.
The torus version improves it even more by reducing the longest path (diameter).

Example (4×4 Mesh = 16 nodes):

  • Degree = 4 (each node connects to top, bottom, left, and right)

  • Diameter ≈ 2√n = 6 (corner to corner)

  • Bisection Width = √n = 4 (cutting a row or column in the center splits it)

3. 3D Mesh / Torus

Define:
Nodes are placed in a 3D grid, forming layers of 2D meshes.
Torus version includes wrap-around connections in all 3 dimensions.

Explanation:
Highly scalable for large systems like supercomputers.
Shorter paths and more parallel communication routes.
Good fault tolerance due to multiple paths.

Example (3×3×3 Mesh = 27 nodes):

  • Degree = 6 (each node connects in x, y, and z directions)

  • Diameter ≈ 3∛n = 6 (longest distance between two corners)

  • Bisection Width ≈ n²/³ = 9 (cutting one middle plane splits the network)

4. Binary Tree

Define:
A hierarchical structure where each node connects to a parent and two children (except leaves and root).
Starts with a single root node at the top.

Explanation:
Efficient for broadcasting (one-to-many communication).
Low communication time between levels.
Weak in fault tolerance—if the root or a high-level node fails, the lower part is cut off.

Example (Full Binary Tree with 7 nodes, height = 2):

  • Degree = 3 (internal nodes connect to parent and 2 children)

  • Diameter ≈ 2 log₂n = 4 (distance between leftmost and rightmost leaf)

  • Bisection Width = 1 (cutting the root breaks the whole network)

5. Hypercube

Define:
A d-dimensional cube where each node connects to others by changing only one bit in its binary address.
For n nodes, d = log₂n.

Explanation:
Very efficient for communication—shortest paths and many routes available.
Used in high-performance computing due to fast routing and high bandwidth.
However, it's harder to build as the number of nodes increases.

Example (3D Hypercube = 8 nodes):

  • Degree = log₂n = 3 (each node connects to 3 others)

  • Diameter = log₂n = 3 (maximum number of hops to reach any node)

  • Bisection Width = n / 2 = 4 (cutting half the links splits the network evenly)

Comments

Post a Comment

Popular posts from this blog

Asymmetric-key algorithms are algorithms used in cryptography that use two different keys  a public key for encryption and a private key for decryption. These keys are mathematically related, but the private key cannot be easily derived from the public key. Types: RSA (Rivest–Shamir–Adleman): It uses large prime numbers to generate the key pair and supports both encryption and digital signatures DSA (Digital Signature Algorithm): DSA is primarily used for creating digital signatures, ensuring the authenticity. Symmetric-key algorithms are algorithms for cryptography that use the same cryptographic keys for both encryption of plaintext and decryption of ciphertext  Types: Stream Cipher:  Stream Cipher Converts the plain text into cipher text by taking 1 byte of plain text at a time. Block cipher: Converts the plain text into cipher text by taking plain text's block at a time DES? DES stands for Data Encryption Standard . It is a symmetric-key algorithm used to enc...
Post a Comment
Read more

Ai Mental Health & Cyber Safety Presentation

Module A - The Normalization Engine Linguistic Challenge: Roman Urdu lacks standardized orthography (e.g., "kesa" vs "kaisa"), creating orthographic "noise" that significantly degrades the accuracy of downstream AI models. Technical Role: Acts as a Sequence-to-Sequence (Seq2Seq) transliteration and lexical normalization layer to standardize inputs before analysis. Model: A specialized transformer architecture, specifically m2m100 fine-tuned on parallel corpora or UrduParaphraseBERT. Primary Dataset: Roman-Urdu-Parl (RUP). A large-scale parallel corpus of 6.37 million sentence pairs designed to support machine transliteration and word embedding training. Link: https://arxiv.org/abs/2503.21530 Outcome: Reduces orthographic noise by achieving up to 97.44% Char-BLEU accuracy for Roman-Urdu to Urdu conversion, ensuring Module B receives high-quality "clean" data for risk analysis. Module B - Risk Stratification (BERT) Heading: The "Safety ...
Post a Comment
Read more